Show simple item record

dc.contributor.authorCarter, Boben_US
dc.contributor.authorPark, Kihongen_US
dc.date.accessioned2011-09-14T20:05:19Z
dc.date.available2011-09-14T20:05:19Z
dc.date.issued1994-11-10
dc.identifier.citationCarter, Robert; Park, Kihong. "On the effectiveness of genetic search in combinatorial optimization”, Technical Report BUCS-1994-010, Computer Science Department, Boston University, November 10, 1994. [Available from: http://hdl.handle.net/2144/1489]
dc.identifier.urihttps://hdl.handle.net/2144/1489
dc.description.abstractIn this paper, we study the efficacy of genetic algorithms in the context of combinatorial optimization. In particular, we isolate the effects of cross-over, treated as the central component of genetic search. We show that for problems of nontrivial size and difficulty, the contribution of cross-over search is marginal, both synergistically when run in conjunction with mutation and selection, or when run with selection alone, the reference point being the search procedure consisting of just mutation and selection. The latter can be viewed as another manifestation of the Metropolis process. Considering the high computational cost of maintaining a population to facilitate cross-over search, its marginal benefit renders genetic search inferior to its singleton-population counterpart, the Metropolis process, and by extension, simulated annealing. This is further compounded by the fact that many problems arising in practice may inherently require a large number of state transitions for a near-optimal solution to be found, making genetic search infeasible given the high cost of computing a single iteration in the enlarged state-space.en_US
dc.description.sponsorshipNSF (CCR-9204284)en_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1994-010
dc.titleOn the Effectiveness of Genetic Search in Combinatorial Optimizationen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record