Memetic algorithm: Difference between revisions

</ref> [[hyper-heuristic]]<ref name=kendall2002cfa>{{cite conference|author=Kendall G. and Soubeiga E. and Cowling P.|title=Choice function and random hyperheuristics|conference=4th Asia-Pacific Conference on Simulated Evolution and Learning. SEAL 2002|pages=667–671|url=http://www.cs.nott.ac.uk/~pszgxk/aim/2008/coursework/paper4.pdf}}</ref><ref name=burke2013>{{cite journal|author1=Burke E. K. |author2=Gendreau M. |author3=Hyde M. |author4=Kendall G. |author5=Ochoa G. |author6=Ouml |author7=zcan E. |author8=Qu R. |title=Hyper-heuristics: A Survey of the State of the Art |journal=Journal of the Operational Research Society |year=2013 |volume=64 |pages=1695–1724 |issue=12 |doi=10.1057/jors.2013.71|citeseerx=10.1.1.384.9743|s2cid=3053192 }}</ref> and meta-Lamarckian MA<ref name=ong2004mll>{{cite journal|author1=Y. S. Ong |author2=A. J. Keane |name-list-style=amp |title=Meta-Lamarckian learning in memetic algorithms|journal=IEEE Transactions on Evolutionary Computation |year=2004 |volume=8 |pages=99–110 |doi=10.1109/TEVC.2003.819944|issue=2|s2cid=11003004 |url=https://eprints.soton.ac.uk/22794/1/ong_04.pdf }}</ref><ref name=":0">{{Cite journal |last=Jakob |first=Wilfried |date=September 2010 |title=A general cost-benefit-based adaptation framework for multimeme algorithms |url=http://link.springer.com/10.1007/s12293-010-0040-9 |journal=Memetic Computing |language=en |volume=2 |issue=3 |pages=201–218 |doi=10.1007/s12293-010-0040-9 |s2cid=167807 |issn=1865-9284|url-access=subscription }}</ref> are referred to as second generation MA exhibiting the principles of memetic transmission and selection in their design. In Multi-meme MA, the memetic material is encoded as part of the [[genotype]]. Subsequently, the decoded meme of each respective individual/[[chromosome]] is then used to perform a local refinement. The memetic material is then transmitted through a simple inheritance mechanism from parent to offspring(s). On the other hand, in hyper-heuristic and meta-Lamarckian MA, the pool

The learning method/meme used has a significant impact on the improvement results, so care must be taken in deciding which meme or memes to use for a particular optimization problem.<ref name="kendall2002cfa" /><ref name="ong2006cam" /><ref name="hart1994ago" /> The frequency and intensity of individual learning directly define the degree of evolution (exploration) against individual learning (exploitation) in the MA search, for a given fixed limited computational budget. Clearly, a more intense individual learning provides greater chance of convergence to the local optima but limits the amount of evolution that may be expended without incurring excessive computational resources. Therefore, care should be taken when setting these two parameters to balance the computational budget available in achieving maximum search performance. When only a portion of the population individuals undergo learning, the issue of which subset of individuals to improve need to be considered to maximize the utility of MA search. Last but not least, it has to be decided whether the respective individual should be changed by the learning success (Lamarckian learning) or not (Baldwinian learning). Thus, the following five design questions<ref name=":0" /><ref name="hart1994ago" /><ref>{{Cite journal |last1=Hart |first1=William E. |last2=Krasnogor |first2=Natalio |last3=Smith |first3=Jim E. |date=September 2004 |title=Editorial Introduction Special Issue on Memetic Algorithms |url=https://direct.mit.edu/evco/article/12/3/v-vi/1185 |journal=Evolutionary Computation |language=en |volume=12 |issue=3 |pages=v–vi |doi=10.1162/1063656041775009 |s2cid=9912363 |issn=1063-6560|url-access=subscription }}</ref> must be answered, the first of which is addressed by all of the above 2nd generation representatives during an MA run, while the extended form of meta-Lamarckian learning of <ref name=":0" /> expands this to the first four design decisions.

It is to be decided whether a found improvement is to work only by the better fitness (Baldwinian learning) or whether also the individual is adapted accordingly (lamarckian learning). In the case of an EA, this would mean an adjustment of the genotype. This question has been controversially discussed for EAs in the literature already in the 1990s, stating that the specific use case plays a major role.<ref>{{Cite journal |last1=Gruau |first1=Frédéric |last2=Whitley |first2=Darrell |date=September 1993 |title=Adding Learning to the Cellular Development of Neural Networks: Evolution and the Baldwin Effect |url=https://direct.mit.edu/evco/article/1/3/213-233/1109 |journal=Evolutionary Computation |language=en |volume=1 |issue=3 |pages=213–233 |doi=10.1162/evco.1993.1.3.213 |s2cid=15048360 |issn=1063-6560|url-access=subscription }}</ref><ref>{{Citation |last1=Orvosh |first1=David |last2=Davis |first2=Lawrence |title=Shall We Repair? Genetic Algorithms, Combinatorial Optimization, and Feasibility Constraints |date=1993 |work=Conf. Proc. of the 5th Int. Conf. on Genetic Algorithms (ICGA) |pages=650 |editor-last=Forrest |editor-first=Stephanie |place=San Mateo, CA, USA |publisher=Morgan Kaufmann |isbn=978-1-55860-299-1 |s2cid=10098180 }}</ref><ref>{{Citation |last1=Whitley |first1=Darrell |title=Lamarckian evolution, the Baldwin effect and function optimization |date=1994 |url=http://link.springer.com/10.1007/3-540-58484-6_245 |work=Parallel Problem Solving from Nature — PPSN III |volume=866 |pages=5–15 |editor-last=Davidor |editor-first=Yuval |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-58484-6_245 |isbn=978-3-540-58484-1 |access-date=2023-02-07 |last2=Gordon |first2=V. Scott |last3=Mathias |first3=Keith |editor2-last=Schwefel |editor2-first=Hans-Paul |editor3-last=Männer |editor3-first=Reinhard|url-access=subscription }}</ref> The background of the debate is that genome adaptation may promote [[premature convergence]]. This risk can be effectively mitigated by other measures to better balance breadth and depth searches, such as the use of [[Population model (evolutionary algorithm)|structured populations]].<ref name=":0" />

More recent applications include (but are not limited to) [[business analytics]] and [[data science]],<ref name=MAs-in-Data-Science-and-Business-Analytics> </ref> training of [[artificial neural network]]s,<ref name=training_ANN>{{cite conference |author1=Ichimura, T. |author2=Kuriyama, Y. |title=Learning of neural networks with parallel hybrid GA using a royal road function|conference=IEEE International Joint Conference on Neural Networks|volume=2|pages=1131–1136|year=1998|location=New York, NY |doi=10.1109/IJCNN.1998.685931 }}</ref> [[pattern recognition]],<ref name=pattern_recognition>{{cite journal|author1=Aguilar, J. |author2=Colmenares, A. |year=1998|title=Resolution of pattern recognition problems using a hybrid genetic/random neural network learning algorithm|journal=Pattern Analysis and Applications|volume=1|issue=1|pages=52–61|doi=10.1007/BF01238026|s2cid=15803359 }}</ref> robotic [[motion planning]],<ref name=motion_planning>{{cite book|author1=Ridao, M. |author2=Riquelme, J. |author3=Camacho, E. |author4=Toro, M. |title=Tasks and Methods in Applied Artificial Intelligence |chapter=An evolutionary and local search algorithm for planning two manipulators motion | year=1998|volume=1416| pages=105–114|publisher=Springer-Verlag|doi=10.1007/3-540-64574-8_396|series=Lecture Notes in Computer Science|isbn=978-3-540-64574-0|citeseerx=10.1.1.324.2668 }}</ref> [[charged particle beam|beam]] orientation,<ref name=beam_orientation>{{cite journal|author1=Haas, O. |author2=Burnham, K. |author3=Mills, J. |year=1998 |title=Optimization of beam orientation in radiotherapy using planar geometry|journal=Physics in Medicine and Biology|volume=43|issue=8|pages=2179–2193|doi=10.1088/0031-9155/43/8/013|pmid=9725597|bibcode=1998PMB....43.2179H |s2cid=250856984 }}</ref> [[circuit design]],<ref name=circuit_design>{{cite journal|author1=Harris, S. |author2=Ifeachor, E. |year=1998|title=Automatic design of frequency sampling filters by hybrid genetic algorithm techniques|journal=IEEE Transactions on Signal Processing |volume=46 |issue=12 |pages=3304–3314 |doi=10.1109/78.735305 |bibcode=1998ITSP...46.3304H }}</ref> electric service restoration,<ref name=service_restoration>{{cite journal|author1=Augugliaro, A. |author2=Dusonchet, L. |author3=Riva-Sanseverino, E. |year=1998|title=Service restoration in compensated distribution networks using a hybrid genetic algorithm|journal=Electric Power Systems Research|volume=46|issue=1|pages=59–66|doi=10.1016/S0378-7796(98)00025-X|bibcode=1998EPSR...46...59A }}</ref> medical [[expert system]]s,<ref name=medical_expert_system>{{cite journal|author1=Wehrens, R. |author2=Lucasius, C. |author3=Buydens, L. |author4=Kateman, G. |year=1993|title=HIPS, A hybrid self-adapting expert system for nuclear magnetic resonance spectrum interpretation using genetic algorithms|journal=Analytica Chimica Acta|volume=277|issue=2|pages=313–324|doi=10.1016/0003-2670(93)80444-P|bibcode=1993AcAC..277..313W |hdl=2066/112321 |s2cid=53954763 |hdl-access=free}}</ref> [[single machine scheduling]],<ref name=single_machine_sched>{{cite conference|author1=França, P. |author2=Mendes, A. |author3=Moscato, P. |title=Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times|conference=Proceedings of the 5th International Conference of the Decision Sciences Institute|pages=1708–1710|year=1999|location=Athens, Greece|s2cid=10797987 }}</ref> automatic timetabling (notably, the timetable for the [[NHL]]),<ref name="nhl_timetabling">{{cite journal | last=Costa | first=Daniel | title=An Evolutionary Tabu Search Algorithm And The NHL Scheduling Problem | journal=INFOR: Information Systems and Operational Research | volume=33 | issue=3 | year=1995 | doi=10.1080/03155986.1995.11732279 | pages=161–178| s2cid=15491435 }}</ref> [[Schedule (workplace)|manpower scheduling]],<ref name=nurse_rostering>{{cite conference|author=Aickelin, U.|title=Nurse rostering with genetic algorithms|conference=Proceedings of young operational research conference 1998|year=1998|location=Guildford, UK|arxiv=1004.2870}}</ref> [[nurse rostering problem|nurse rostering optimisation]],<ref name=nurse_rostering_function_opt>{{cite book| author = Ozcan, E.|title=Practice and Theory of Automated Timetabling VI|year=2007|chapter=Memes, Self-generation and Nurse Rostering|volume=3867|pages=85–104|publisher=Springer-Verlag|doi=10.1007/978-3-540-77345-0_6|series=Lecture Notes in Computer Science|isbn=978-3-540-77344-3}}</ref> [[Scheduling (computing)#Operating system process scheduler implementations|processor allocation]],<ref name=proc_alloc>{{cite journal|author1=Ozcan, E. |author2=Onbasioglu, E. |year=2007|title=Memetic Algorithms for Parallel Code Optimization|journal=International Journal of Parallel Programming|volume=35|issue=1|pages=33–61|doi=10.1007/s10766-006-0026-x|s2cid=15182941 }}</ref> maintenance scheduling (for example, of an electric distribution network),<ref name=planned_maintenance>{{cite journal|author1=Burke, E. |author2=Smith, A. |year=1999|title=A memetic algorithm to schedule planned maintenance for the national grid| journal=Journal of Experimental Algorithmics |issue=4|pages=1–13 |doi=10.1145/347792.347801 |volume=4|s2cid=17174080 |doi-access=free}}</ref> [[Scheduling (production processes)|scheduling]] of multiple [[Workflow|workflows]] to constrained heterogeneous resources,<ref>{{Cite journal |last1=Jakob |first1=Wilfried |last2=Strack |first2=Sylvia |last3=Quinte |first3=Alexander |last4=Bengel |first4=Günther |last5=Stucky |first5=Karl-Uwe |last6=Süß |first6=Wolfgang |date=2013-04-22 |title=Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing |journal=Algorithms |language=en |volume=6 |issue=2 |pages=245–277 |doi=10.3390/a6020245 |issn=1999-4893|doi-access=free }}</ref> multidimensional knapsack problem,<ref name=mkp_ma>{{cite journal|author1=Ozcan, E. |author2=Basaran, C. |year=2009|title=A Case Study of Memetic Algorithms for Constraint Optimization|journal=Soft Computing: A Fusion of Foundations, Methodologies and Applications |volume=13|issue=8–9 |pages=871–882 |doi=10.1007/s00500-008-0354-4 |citeseerx=10.1.1.368.7327 |s2cid=17032624 }}</ref> [[VLSI]] design,<ref name="vlsi_design">{{cite journal |author=Areibi |first1=S. |last2=Yang |first2=Z. |year=2004 |title=Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering |journal=Evolutionary Computation |volume=12 |issue=3 |pages=327–353 |doi=10.1162/1063656041774947 |pmid=15355604 |s2cid=2190268}}</ref> [[cluster analysis|clustering]] of [[expression profiling|gene expression profiles]],<ref name=clustering_gene_expression >{{cite book|author1=Merz, P. |author2=Zell, A. |title = Parallel Problem Solving from Nature — PPSN VII|volume=2439 |year=2002|publisher=[[Springer Science+Business Media|Springer]]|doi=10.1007/3-540-45712-7_78|pages=811–820| chapter=Clustering Gene Expression Profiles with Memetic Algorithms|series=Lecture Notes in Computer Science |isbn=978-3-540-44139-7 }}</ref> feature/gene selection,<ref name=gene_selection1>{{cite journal|author=Zexuan Zhu, Y. S. Ong and M. Dash|title=Markov Blanket-Embedded Genetic Algorithm for Gene Selection|year=2007|journal=Pattern Recognition|volume=49|issue=11|pages=3236–3248|doi=10.1016/j.patcog.2007.02.007|bibcode=2007PatRe..40.3236Z}}</ref><ref name=gene_selection2>{{cite journal|author=Zexuan Zhu, Y. S. Ong and M. Dash|title=Wrapper-Filter Feature Selection Algorithm Using A Memetic Framework|year=2007|journal=IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics|volume=37|issue=1|pages=70–76|doi=10.1109/TSMCB.2006.883267|pmid=17278560|hdl=10338.dmlcz/141593|s2cid=18382400|hdl-access=free}}</ref> parameter determination for hardware fault injection,<ref>{{Cite web|title=Artificial Intelligence for Fault Injection Parameter Selection {{!}} Marina Krček {{!}} Hardwear.io Webinar|url=https://hardwear.io/webinar/AI-for-fault-injection-parameter-selection.php|access-date=2021-05-21|website=hardwear.io}}</ref> and multi-class, multi-objective [[feature selection]].<ref>{{Cite journal |last1=Zhu |first1=Zexuan |last2=Ong |first2=Yew-Soon |last3=Zurada |first3=Jacek M |date=April 2010 |title=Identification of Full and Partial Class Relevant Genes |url=https://ieeexplore.ieee.org/document/4653480 |journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics |volume=7 |issue=2 |pages=263–277 |doi=10.1109/TCBB.2008.105 |pmid=20431146 |s2cid=2904028 |issn=1545-5963|url-access=subscription }}</ref><ref name=feature_selection2>{{cite book|author1=G. Karkavitsas |author2=G. Tsihrintzis |title=Intelligent Interactive Multimedia Systems and Services |chapter=Automatic Music Genre Classification Using Hybrid Genetic Algorithms |name-list-style=amp |year=2011|volume=11|pages=323–335|publisher=Springer|doi=10.1007/978-3-642-22158-3_32|series=Smart Innovation, Systems and Technologies |isbn=978-3-642-22157-6 |s2cid=15011089 }}</ref>