According to Photokano, Yosuga no Sora and Amagami-SS (series that adapted from Visual Novel) are animated as multiple story-lines in one series. When did this trend begin, and which anime might be earliest version?
Short answer: Amagami SS was probably the first anime of this type.
Long answer: First, let's get some terminology down. Anime in which multiple storylines without shared continuity are released as a single production are typically referred to as "omnibus" anime. Omnibus anime are typically (though not necessarily always) adapted from visual novels or other computer games, which lend themselves well to separate continuities,* and typically have each continuity correspond to the protagonist's relationship with a particular person.
To clarify what "omnibus" means, let me point out some anime that are not considered omnibus by this definition.
- Clannad is not an omnibus anime because there is a single continuity. Everything Tomoya (the protagonist) experiences during Kotomi's arc (episodes 10-14) stays with him (and everyone else) from episode 15 onwards.
- Amnesia is not an omnibus anime even though the timeline gets reset every few episodes, since the protagonist remembers what happened to her before each reset.
With this definition of "omnibus" in place, the question, then, is: which was the first omnibus anime?
There is strong evidence from the archives of /a/ that the term "omnibus" only began to be used in this sense starting in July 2010. This is the same month that Amagami began airing. A perusal of those discussions strongly suggests that the omnibus format was a novel innovation in anime at the time. Furthermore, I cannot find any references to omnibus-style anime existing prior to Amagami SS. Taken together, all this evidence leads me to believe that Amagami SS was the first omnibus anime.
Aside: as Logan M noted in a comment, omnibus-style manga have existed for a long time. Amagami SS's use of the omnibus format was novel only for its medium, not for Japanese popular media in general or anything like that.