Рассмотрение классов параллельных генетических алгоритмов. Построение островной модели параллельных генетических алгоритмов. Основные проблемы, решаемые при моделировании генетических алгоритмов. Схема работы буферной модели разработанного алгоритма.
Аннотация к работе
Эволюционные алгоритмы (ЭА) - это стохастический метод поиска, который применялся для решения множества проблем поиска, оптимизации и машинного обучения [1, 2]. В отличие от большинства других технологий оптимизации, ЭА содержат популяцию пробных решений, которые конкурентно управляются по средствам применения некоторых различных операторов для поиска достоверного, если не глобального, оптимального решения. Генетические алгоритмы итеративно обучают популяцию индивидов, применяя оператор рекомбинации (объединяя двух или более родителей для получения одного или более потомков) и мутации их содержимого (случайное изменение проблемных переменных). Однако если придерживаться законов естественной эволюции, нельзя управлять одной популяцией, в которой взятая особь претендует на скрещивание с какими-либо другими партнерами в той же популяции (беспорядочное скрещивание). Среди расширений типов ГА особенно популярны. распределенные ГА (РГА) [3-5], Распределенные эволюционные алгоритмы - это подкласс параллельных генетических алгоритмов, предназначенных для снижения преждевременной сходимости к локальному оптимуму, стимуляции разнообразия и поиска альтернативных решений той же проблемы.Существует три главных типа параллельных ПГА [7]: 1) глобальные однопопуляционные ПГА, модель «хозяин-раб» (или «мастер - подчиненные» (Master-Slave GAS); В алгоритмах первого типа существует главная популяция, но оценка целевой функции (ЦФ) распределена среди нескольких процессоров. Хозяин хранит популяцию, выполняет операции ГА и распределяет индивидуумы между подчиненными. Так как в таких параллельных ГА селекция и кроссинговер работают с целой популяцией, их называют глобально параллельными ГА. Многопопуляционные (или многообщинные) ГА более сложны, так как они состоят из нескольких подпопуляций, которые периодически обмениваются индивидуумами (схема на рис.1).При этом Гроссо имитировал диплоидных особей (использовались две субкомпоненты для каждого «гена»), и популяция была разделена на 5 общин. Каждая община обменивалась индивидуумами со всеми другими общинами при установлении фиксированных коэффициентов миграции. Экспериментальным путем Гроссо определил, что улучшение средней ЦФ популяции происходило быстрее при маленьких общинах, чем при одиночной популяции. Однако при средних коэффициентах миграции разделенная популяция нашла решения, схожие с теми, что найдены для одиночной популяции. Как и Гроссо, авторы этой статьи указывают, что параллельные ГА с высоким уровнем коммуникации находят решения того же качества, что и последовательный ГА с большой одиночной популяцией.Топология сети - это важный фактор в производительности параллельного алгоритма, потому что она определяет, как быстро (или как медленно) хорошее решение распространяется в другие популяции. Если сеть является сильно связной, то хорошие решения будут быстро распространяться во все общины и могут быстро «насытить» популяцию. С другой стороны, если сеть слабо связная, решения будут распространяться медленнее и общины будут более изолированными друг от друга (обеспечивается возможность появления различных решений). В этом случае община не ограничена связями с некоторым фиксированным количеством общин; вместо этого мигранты посылаются в общины, которые удовлетворяют некоторому критерию. В качестве подобного критерия берется мера разнообразия популяции или мера генотипического расстояния между двумя популяциями (или расстояния от характерной особи популяции, например, наилучшей).Научные интересы авторов статьи связаны с исследованием влияния структуры взаимосвязей параллельного ГА на эффективность алгоритма в целом. Авторами предлагается следующая модель, схематически изображенная на рис.2. параллельный генетический алгоритм модель Модель можно представить как структуру типа «звезда», взаимодействующую с популяциями через так называемый буфер хромосом. II При наступлении определенной ситуации в популяции, эта популяция обращается в буфер и забирает оттуда часть или все хромосомы, затем добавляет туда часть своих особей. Достоинство этой модели заключается в большой гибкости, она позволит провести исследования различных стратегий и критериев работы параллельных генетических алгоритмов.Возможности современных вычислительных устройств можно использовать на полную мощность только в асинхронных моделях, поскольку сложность оптимизационных задач возрастает параллельно с необходимостью быстрого принятия компанией решений в условиях сложной экономической обстановки.
Список литературы
1. Back T., Fogel D.B., Michalewicz Z. Handbook of Evolutionary Computation// Oxford: Oxford University Press, 1997.
2. Michalewicz Z. Genetic Algorithms Data Structures = Evolution Programs. // Berlin: Springer Verlag, 1992.
3. Alba E., Troya J.M. A Survey of Parallel Distributed Genetic Algorithms// Complexity. 1999. Vol.4, № 4. P. 31-52.
4. Alba E., Troya J.M. Influence of the Migration Policy in Parallel Distributed GAS with Structured and Panmictic Populations// Application Intelligence. 2000. Vol.12, №3. P. 163-181.
5. Alba E., Troya J.M. Analyzing Synchronous and Asynchronous Parallel Distributed Genetic Algorithms// Future Generation Computer Systems. 2001. Vol.17, №4. P. 451-465.
6. Golub M., Jakobovic D. A New Model of Global Parallel Genetic Algorithm// proceedings of 22nd International Conference on Information Technology Interfaces IVI. 2000. P. 363-368.
7. Cantu-Paz E. A Survey of Parallel Genetic Algorithms// ILLIGAL Report, 1997.
8. Grosso P.B. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Interaction in a Multilocus Model// Unpublished doctoral dissertation, The University of Michigan. (University Microfilms №8520908), 1985.
9. Pettey C.B., Leuze M.R., Grefenstette J.J. A Parallel Genetic Algorithm// Grefenstette J. J., Ed., Proceedings of the Second International Conference on Genetic Algorithms. Hillsdale NJ: Lawrence Erlbaum Associates, 1987. P. 155-161.
10. Tanese R. Parallel Genetic Algorithm for a Hypercube// Proceedings of the Second International Conference on Genetic Algorithms/ Ed. by J.J. Grefenstette.- Hillsdale NJ: Lawrence Erlbaum Associates, 1987. P. 177-183.
11. Cohoon J.P., Hegde S.U., Martin W.N., Richards D. Punctuated Equilibria: A Parallel Genetic Algorithm// Proceedings of the Second International Conference on Genetic Algorithms/ Ed. by J.J. Grefenstette. Hillsdale NJ: Lawrence Erlbaum Associates, 1987. P. 148-154.
12. Cohoon J.P., Martin W.N., Richards D.S. Genetic Algorithms and Punctuated Equilibria in VLSI// Parallel Problem Solving from Nature/ Ed. by H.-P.Schwefel, R.Manner R. Berlin: Springer Verlag,1991. P. 134-144.
13. Cohoon J. P., Martin W. N., Richards D. S. A Multi-Population Genetic Algorithm for Solving the K-Partition Problem on Hyper-Cubes// Proceedings of the Fourth International Conference on Genetic Algorithms/ Ed. by R.K. Belew, L.B.Booker. San Mateo CA: Morgan Kaufmann, 1991. P. 244-248.