著者

齊藤進

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.59, pp.5-8, 2002-06-26

---

ウイルス進化論を模した遺伝的アルゴリズムが開発され、組み合わせ問題に適用された。この研究におけるアルゴリズムはひとつの個体とたくさんのウイルスを用いる。個体はウイルスにより攻撃され、感染され、改良される。ウイルスは二つの遺伝子(トップ遺伝子とテイル遺伝子)からなる。もし個体が攻撃によって改善されれば、感染が起こる。局所解を抜け出すために、感染に余裕率を設けている。感染後、ウイルスのテイル遺伝子は突然変異される。もし同じウイルスが数回攻撃し、感染しなかったならば、トップ遺伝子が突然変異される。個体はこの突然変異により、効率的に改善される。最適解を得るために、部分攻撃がまた有効である。A genetic algorithm that simulates the virus evolutionary theory has been developed and applied to combinatorial optimization problems. The algorithm in this study uses only one individual and a population of viruses. The individual is attacked, infected and improved by the viruses. The viruses are composed of two genes (a top gene and a tail gene). If the individual is improved by the attack, infection occurs. To escape from local minima, an infection allowance is set. After the infection, the tail genes are mutated. If the same virus attacks several times and fails to infect, the top genes of the virus are mutated. The individual can be improved effectively using this mutation. To obtain the optimal solution, "sub-attack" is also useful.