Preventing Early Convergence in Genetic Programming by Replacing Similar Programs

Created by W.Langdon from gp-bibliography.bib Revision:1.4333

  title =        "Preventing Early Convergence in Genetic Programming by
                 Replacing Similar Programs",
  author =       "Dylan Mawhinney",
  year =         "2000",
  month =        oct # "~31",
  school =       "RMIT",
  address =      "Australia",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  citeseer-isreferencedby = "oai:CiteSeerPSU:86939;
                 oai:CiteSeerPSU:207908; oai:CiteSeerPSU:211636;
                 oai:CiteSeerPSU:66071; oai:CiteSeerPSU:82846",
  citeseer-references = "oai:CiteSeerPSU:188996; oai:CiteSeerPSU:322830;
                 oai:CiteSeerPSU:18409; oai:CiteSeerPSU:9503;
                 oai:CiteSeerPSU:500714; oai:CiteSeerPSU:189501;
                 oai:CiteSeerPSU:32228; oai:CiteSeerPSU:189578;
                 oai:CiteSeerPSU:17731; oai:CiteSeerPSU:189766;
                 oai:CiteSeerPSU:269924; oai:CiteSeerPSU:125377;
                 oai:CiteSeerPSU:300709; oai:CiteSeerPSU:194398;
                 oai:CiteSeerPSU:229338; oai:CiteSeerPSU:48471;
                 oai:CiteSeerPSU:142868; oai:CiteSeerPSU:144102;
                 oai:CiteSeerPSU:28466; oai:CiteSeerPSU:308722;
                 oai:CiteSeerPSU:62810; oai:CiteSeerPSU:191318",
  annote =       "The Pennsylvania State University CiteSeer Archives",
  language =     "en",
  oai =          "oai:CiteSeerPSU:451316",
  rights =       "unrestricted",
  size =         "39 pages",
  abstract =     "Genetic programming is a means of automatically
                 evolving programs to perform a particular task or solve
                 a particular problem using the Darwinian principle of
                 survival of the fittest. Many genetic programming
                 problems can suffer from early convergence, that is,
                 the genetic programming run terminates before the
                 optimal program has evolved. Early convergence is a
                 hindrance to genetic programming especially for
                 problems which need signi cant amounts of computing
                 time. This project describes a method of preventing
                 early convergence by replacing similar programs. A
                 percentage of the most similar programs are replaced by
                 randomly generated programs. This method uses the
                 number of changes reported by the UNIX program diff to
                 estimate how similar a program is to the rest of the
                 population. We performed experiments using no
                 replacement and replacement on the MAX problem, a
                 problem known to suffer from early convergence, and the
                 Robocup simulator league domain. Using a replacement
                 rate of 10% in the MAX domain, increased the success
                 rate from 16% (using no replacement) to 42%. Performing
                 similarity replacement in the Robocup domain increased
                 the number of runs which obtained successful players,
                 from 2 out of the 5 runs using no replacement, to 4 out
                 of the 5 runs using 10% replacement. The quality of the
                 players in the successful runs was also improved.
                 Performing replacement every 2nd, 5th, or 10th
                 generation did not significantly reduce the number of
                 successful runs in the MAX domain when using a
                 replacement rate of 10%. Replacing a percentage of the
                 most similar programs prevented early convergence more
                 often than when no replacement was used. Our results
                 suggest that performing similarity replacement is
                 worthwhile in problems where the cost of computing the
  notes =        "Honours thesis? RMIT.EDU.AU down at present See also

Genetic Programming entries for Dylan Mawhinney