Дискретные задачи размещения Оптимизационные алгоритмы

Главная страница библиотеки  Демонстрационная версия Оптимизационные алгоритмы

Генетические алгоритмы

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов [7, 12]. Примерно через десять лет появились первые теоретические обоснования этого подхода [16, 21, 22]. На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач [6, 15] и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:
http://www.natural-selection.com/eps/
http://mat.gsia.cmu.edu/Conferences/   .

Общую схему генетических алгоритмов проще всего понять, рассматривая задачи безусловной оптимизации

max { f (i) | i{0,1}ⁿ }.

Примерами служат задачи размещения, стандартизации, выполнимости и другие [2, 5, 19]. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции I₀ = {i₁, i₂, …, i_s} — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов [1, 3, 4]. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения, родители i₁, i₂. Оператор скрещивания по решениям i₁, i₂ строит новое решение i' , которое затем подвергается небольшим случайным модификациям, которые принято называть  мутациями. Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции. Общая схема такого алгоритма может быть записана следующим образом.

Генетический алгоритм

1. Выбрать начальную популяцию I₀ и положить
    f*  = max { f (i) | i I₀}, k : = 0.

2. Пока не выполнен критерий остановки делать следующее.

        2.1. Выбрать родителей i₁, i₂ из популяции I_k.
        2.2. Построить i' по i₁, i₂.
        2.3. Модифицировать i' .
        2.4. Если f* < f (i' ), то f* : = f (i' ).
        2.5. Обновить популяцию и положить k : = k+1.

Остановимся подробнее на основных операторах этого алгоритма: селекции, скрещивании и мутации. Среди операторов селекции наиболее распространенными являются два вероятностных оператора пропорциональной и турнирной селекции. При пропорциональной селекции вероятность на k-м шаге выбрать решение i в качестве одного из родителей задается формулой

в предположении, что f (i) > 0 для всех i Î I. При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирная селекция имеет определенные преимущества перед пропорциональной, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.

Как только два решения выбраны, к ним применяется вероятностный оператор скрещивания (crossover). Существует много различных версий этого оператора [15], среди которых простейшим, по видимому, является однородный оператор. По решениям i₁, i₂ он строит решение i' присваивая каждой координате этого вектора с вероятностью 0,5 соответствующее значение одного из родителей. Если вектора i₁, i₂ совпадали скажем по первой координате, то вектор i'  "унаследует" это значение. Геометрически, оператор скрещивания случайным образом выбирает в гиперкубе вершину i' , которая принадлежит минимальной грани, содержащей вершины i₁, i₂. Можно сказать, что оператор скрещивания старается выбрать новое решение i' где-то между i₁, i₂ полагаясь на удачу. Более аккуратная  процедура могла бы выглядеть таким образом. Новым решением i' является оптимальное решение исходной задачи на соответствующей грани гиперкуба. Конечно, если расстояние Хемминга между i₁, i₂ равно n, то задача оптимального скрещивания совпадает с исходной. Тем не менее даже приближенное решение этой задачи вместо случайного выбора заметно улучшает работу генетического алгоритма [8, 9, 10, 14]. По аналогии с однородным оператором скрещивания легко предложить и другие операторы, использующие не только два, но и произвольное число решений из популяции. Например, в [20] использовалось восемь родителей. Другие примеры можно найти в [13]. С адаптацией этой идеи к задаче коммивояжера можно познакомиться в [17].

Оператор мутации, применяемый к решению i'  в п. 2.3. генетического алгоритма, с заданной вероятностью p_m Î (0, 1) меняет значение каждой координаты на противоположное. Например, вероятность того, что i' = (0, 0, 0, 0, 0) в ходе мутации перейдет в j' = (1, 1, 1, 0, 0), равна p_m ´ p_m ´ p_m ´ (1 – p_m) ´ (1 – p_m) > 0. Таким образом, с ненулевой вероятностью решение i' может перейти в любое другое решение. Отметим, что модификация решения i' может состоять не только в случайной мутации, но и в частичной перестройке решения алгоритмами локального поиска. Применение локального спуска позволяет генетическому алгоритму сосредоточиться только на локальных оптимумах. Множество локальных оптимумов может оказаться экспоненциально большим и на первый взгляд кажется, что такой вариант алгоритма не будет иметь больших преимуществ. Однако экспериментальные исследования распределения локальных оптимумов свидетельствуют о высокой концентрации их в непосредственной близости от глобального оптимума [11, 18]. Это наблюдение известно как гипотеза о существовании "большой долины" для задач на минимум или "центрального горного массива" для задач на максимум.

   Гипотеза 1.
В среднем локальные оптимумы расположены гораздо ближе к глобальному оптимуму чем к случайно выбранной точке. Их распределение в области допустимых решений на является равномерным. Они концентрируются в районе глобального оптимума, занимая область небольшого диаметра.

Эта гипотеза отчасти объясняет работоспособность генетических алгоритмов. Если в популяции собираются локальные оптимумы, которые согласно гипотезе сконцентрированы в одном месте, и очередное решение i' выбирается где-то между двумя произвольными локальными оптимумами, то такой процесс имеет много шансов найти глобальный оптимум. Аналогичные рассуждения объясняют работоспособность и других локальных алгоритмов. В связи с этим проверка и теоретическое обоснование данной гипотезы представляет несомненный интерес.

Литература

1. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т3 (1998), Иркутск, с. 17–20.

2. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения.  Дискретный анализ и исследование операций. Сер. 2. т6 (1999), № 1, с. 12–32.

4. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды,  т1 (1998), Иркутск, с. 249–252.

5. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

6. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

7. Растригин Л. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3–16.

8. Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225–234.

9. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29–49.

10. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107–122.

11. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi–start technique for combinatorial global optimizations. Oper. Res. Lett. v16 (1994), N2,  pp 101-114.

12. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

13. Eiben A. E., Raue P. E., Ruttkay Zs. Genetic Algorithms with multiparent recombination. Parallel Problem Solving from Nature III. Berlin: Springer Verlag, (LNCS), v866 (1994), pp 78-87.

14. Eremeev A. V. A genetic algorithm with a non-binary representation for the set covering problem. Operations Research Proceedings 1998. Berlin: Springer Verlag. 1999. pp 175-181.

15. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

16. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

17. Johnson D. S., McGeoch L. A. The traveling salesman problem: a case study. Local search in combinatorial optimization. Chichester: Wiley, pp 215-310.

18. Kirkpatrick S., Toulouse G. Configuration space analysis of traveling salesman problems.  J. de Phys. v46 (1985) , pp 1277-1292.

19. Mirchandani P. B., Francis R. L. Discrete Location Theory. New York: John Wiley and Sons, 1990.

20. Muhlenbein H. Parallel genetic algorithm, population dynamics and combinatorial optimization. Proc. Third Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989. pp 416-421.

21. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der Biologischen Information, Freiburg: Fromman, 1973.

22. Schwefel H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.

Главная страница библиотеки  Демонстрационная версия Оптимизационные алгоритмы