Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
ую возможность для репродукции, чем слабые хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичные или различные потомки.
Существует много различных видов селекции,рассмотрим основные из них.
Селекция на основе рулетки - это самый простой и наиболее используемый в ПГА метод. При его использовании каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции, причем элемент с большим значением ЦФ имеет большую вероятность для выбора.
Селекция на основе заданной шкалы. Здесь популяция предварительно сортируется от лучшей особи к худшей на основе заданного критерия. Каждому элементу назначается определенное число и далее селекция выполняется согласно этому числу.
Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения ЦФ. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс идет до тех пор, пока продолжают появляться элитные элементы.
Турнирная селекция. При этом некоторое число элементов (согласно размеру турнира) выбирается случайно или направленно из популяции, и лучшие элементы в этой группе на основе заданного турнира определяются для дальнейшего генетического поиска.
Кроме описанных, существует большое число других методов селекции, которые можно условно классифицировать на три группы. К первой группе отнесем вероятностные методы селекции. Ко второй - детерминированные. К третьей - различные комбинации методов из первой и второй групп. Поиски оптимальных методов селекции непрерывно продолжаются. Дело в том, что основной трудностью решения оптимизационных задач с большим количеством локальных оптимумов является предварительная сходимость алгоритмов. Другими словами, происходит попадание решения в один, далеко не самый лучший, локальный оптимум. Различные методы селекции и их модификации как раз и позволяют в некоторых случаях решать проблему предварительной сходимости алгоритмов. Следует отметить, что исследователи ГА все более склоняются к мысли применять комбинированные методы селекции с использованием предварительных знаний о решаемых задачах и предварительных результатах.
Опишем теперь методы кроссинговера. В литературе часто их называют операторами кроссинговера (ОК). Основная функция ОК - создавать хромосомы потомков на основе различного скрещивания родителей. Существует огромное число ОК, так как их структура в основном и определяет эффективность ГА. Кратко рассмотрим основные ОК, известные в литературе, и их модификации.
Одноточечный (простой) ОК. Перед началом работы одноточечного ОК определяется так называемая точка ОК, или разрезающая точка, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть разрезаны. Например, пусть популяция Р состоит из двух хромосом Р={р1, р2}, которые выступают в качестве родителей. Пусть первый и второй родители имеют вид р1: (11111), р2: (00000). Выберем точку ОК между вторым и третьим генами в р1, р2. Тогда, меняя элементы после или перед точкой ОК между двумя родителями, можно создать два новых потомка. В нашем примере получим:
Рисунок 1 - Одноточечный ОК
Итак, одноточечный ОК в интеллектуальной ИС выполняется в три этапа:
.Две хромосомы А = a1, а2,..., aL и В = а1, а2,..., аL выбираются случайно из текущей популяции.
.Число к выбирается из {1, 2,...,L-1} также случайно. Здесь L - длина хромосомы, к-точка ОК (номер или значение, код гена, после которого выполняется разрез хромосомы).
.Две новые хромосомы формируются из А и В путем перестановок элементов согласно правилу
А = a1, a2, … , ak,ak+1,…, aL (4) = a1, a2, … , ak,ak+1,…, aL (5)
После применения OK имеем две старые хромосомы и всегда получаем две новые хромосомы. Схематически простой ОК показывает преобразование двух хромосом и частичный обмен информацией между ними, используя точку разрыва, выбранную случайно.
В двухточечном ОК определяются две точки ОК, и гены обмениваются между ними. Например:
Рисунок 2 - Двухточечный ОК
Отметим, что точки ОК в двухточечном ОК также определяются случайно. Существует много модификаций двухточечного ОК.
Развитием двухточечного ОК является многоточечный ОК или N-точечный ОК, он выполняется аналогично двухточечному ОК, хотя большое число разрезающих точек может привести к потере хороших родительских свойств.
Порядковый ОК. В порядковом ОК разрезающая точка также выбирается случайно. Далее происходит копирование левого сегмента р1 в р1. Остальные позиции в р1 берутся из р2 в упорядоченном виде слева направо, исключая элементы, уже попавшие в р1. Например:
Рисунок 3 - Порядковый ОК
Получение р2 может выполняться различными способами. Наиболее распространенный метод - копирование левого сегмента из р2, а далее анализ р1 методом, указанным выше. Тогда имеем р2 : (G А В Е | С D F Н).
Частично-соответствующий ОК. Здесь также случайно выбирается разрезающая точка или точка ОК. Дальше анализируются сегменты в обоих родителях, и устанавливается частичное соответствие между элементами первого и втор