Paper #1 Review

From: Brian Ferris (bdferris@cs.washington.edu)
Date: Wed Dec 01 2004 - 11:54:21 PST

  • Next message: Harsha V. Madhyastha: "Evolution review"

    In "The evolutionary origin of complex features" by Lenski et. al., an
    attempt is made to experimentally verify one of the fundamental
    concepts in Darwin's theory of evolution. The theory states that
    complex biological features, such as the eye, must evolve over a series
    of incremental adaptations and mutations. While evidence does exist to
    support this model, the inability to examine the complete evolutionary
    history of an organism over time makes support difficult. The authors
    seek to make the complete examination of the evolution of a complex
    feature possible by examining the evolution of digital organisms.

    The experimental setup involved an digital organisms defined uniquely
    as a loop of processing instructions. The environment allowed for
    replication, mutation and competition amongst organisms in the
    following way. Replication is asexual and occured using binary
    fission. Mutation occurred during copying, by way of point mutations,
    insertions, and deletions. Finally, competition was implemented by
    rewarding organisms for performing logic operations. The only logic
    operation available in the base instruction set was a nand-op, from
    which all other operations can be constructed. Reward increased
    exponentially up to EQUALS operation, which is both highest in
    complexity and reward.

    The actual experiment evolved the examination of a case-study group and
    then a few experiments to determine how altering the environment
    affected the evolutionary process. Their examination of genetic lines
    that evolved to include the EQUALS operation raised a number of points.
      First, while there were a large number of positive mutations along the
    line, roughly sixteen percent of the mutations were negative in nature.
      Examinations of these evolutionary backwards moves showed that their
    combination with subsequent mutations lead to highly beneficial
    results, suggesting that evolutionary advancement is not completely
    uphill.

    Another interesting point was that no intermediate logic function, such
    as OR, NOR, XOR, et-cetera, was specifically required in the
    evolutionary path, as all of the genetic lines evolving to EQUALS had a
    case with at least one sub-operation left unimplemented. This point
    was corroborated when they modified the environment to remove the
    reward from specific operations or pairs of operations, and the EQUALS
    operation still consistently evolved.

    One could consider the digital evolution performed in this experiment
    as just another form of search. Each unique collection of processing
    instructions defines a unique organism and a unique state in the search
    space. State transitions occur during replication, with different
    branches encompassing different mutations. The authors point out that
    there are ~5.6 x 10^70 genotypes possible in this search space, so an
    uniformed search is obviously out of the question. However, the two
    points the raised about the properties of the evolutionary path raise
    interesting questions about implementing an informed search.

    The key issue in determining a heuristic for informing EQUALS evolution
    is that genetic lines evolving to success often involved deleterious
    mutations. That is, straight hill climbing towards our goal has to
    navigate multiple local maxima. Thus, informed search would likely
    need to be combined with some stochastic element such as randomly
    ignoring the heuristic or simulated annealing to properly advance the
    search.

    A point I found interesting was that no one sub-operation was key in
    the evolutionary chain of successful genetic lines. I believe the
    selected reward values for performing the various logical operations
    might play some role in the evolutionary cycle, but the details on the
    selection of these weightings was not in-depth and no experiments
    exploring alternate weightings was explored.


  • Next message: Harsha V. Madhyastha: "Evolution review"

    This archive was generated by hypermail 2.1.6 : Wed Dec 01 2004 - 11:53:17 PST