Применение генетических алгоритмов к решению задач дискретной оптимизации

    (1.20)

Задача относится к экстремальным задачам переборного типа, так как общее число допустимых решений равно .

Решения можно кодировать в виде бинарных строк, значения 0 или 1 в i-ой позиции означают принадлежность i-ой вершины к соответствующему подмножеству вершин. Очевидно, что данный способ кодирования допускает существование недопустимых кодировок, поэтому такое представление не является ортогональным.

6.3 Задача о назначениях

Пусть имеется работ и кандидатов на их выполнение, причем назначение j-й работы i-му кандидату требует затрат . Задача состоит в нахождении такого распределения кандидатов по работам, чтобы минимизировать суммарные затраты. Причем каждый кандидат может быть назначен только на одну работу, и каждую работу может выполнять только один кандидат. Математически это можно записать:

       (1.21)

Каждое решение можно закодировать перестановкой, в которой позиция обозначает номер кандидата, а значение в этой позиции – номер работы, назначенной кандидату. Очевидно, что число возможных назначений равно . Для задачи о назначениях n-арный способ кодирования будет обладать свойством ортогональности.

Заключение

Решение задач дискретной оптимизации связано с трудностями принципиального характера. Эффективность точных методов решения задач дискретной оптимизации существенно зависит от размерности, причем с ее возрастанием резко увеличивается объем вычислений, необходимых для отыскания точного решения. Обычно он настолько велик, что точно решить задачу за реальное время невозможно. Поэтому возникает необходимость в выборе эффективных приближенных методов дискретной оптимизации.

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

1. обрабатывают не значения параметров самой задачи, а их закодированную форму;
2. осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;
3. используют только целевую функцию, а не ее производные, либо иную дополнительную информацию;
4. применяют вероятностные, а не детерминированные правила выбора.

Перечисленные четыре свойства, которые можно сформулировать также как кодирование параметров, операции на популяциях, использование минимума информации о задаче и рандомизация операций приводят в результате к устойчивости генетических алгоритмов и к их превосходству над другими широко применяемыми технологиями.

Список использованных источников

1. Батищев, Д. И. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал / Д. И. Батищев, Е. А. Неймарк, Н. В. Старостин. – Нижний Новгород: ННГУ, 2007. – 85 с.
2. Гладков, Л. А. Генетические алгоритмы: Учебное пособие / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. – М.: «Физматлит», 2006. – 320 с.
3. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М.: Горячая линия – Телеком, 2006. – 452 с.