Генетические алгоритмы в изобретательских задачах

Размещено на http://www.allbest.ru/

5

Размещено на http://www.allbest.ru/

Генетические алгоритмы в изобретательских задачах

Введение

Изобретательство - древнейшее занятие человека. С изобретением первых орудий труда и начинается история человека. Затем изобретались новые вещи и технологии их изготовления, отношения между людьми и способы их выяснения, приёмы ведения хозяйства и управления оным, способы делать деньги и считать их.… За тысячи лет, прошедшие с тех пор, все изменилось, неизменным оста­лся только метод создания новых изобретений - метод проб и ошибок (МПиО).

Генетические алгоритмы и алгоритм решения изобретательских задач связывает общее происхождение из эволюционной теории. Генетические алгоритмы используются для поиска оптимального решения путем естественного отбора и наследования. Поиск ответа в АРИЗ представляет собой процесс зарождения, развития и разрешения противоречий. Исходными данными в обоих случаях является изобретательская ситуация, но АРИЗ относится к направленным методам поиска решения, а генетические алгоритмы имеют случайную составляющую.

Как указывает Г.С. Альтшуллер, "изобретательская ситуация представляет собой клубок сложных проблем, и нужно каким-то образом выделить из этого клубка единственно правильную задачу". Правильная задача отыскивается в наиболее "узком" месте этого клубка, там, где выявляется наиболее обостренное противоречие неравномерного развития.

Генетические алгоритмы -- это новая область исследований, которая появилась в результате работ Д. Холланда и его коллег. ГА, описанные Д. Холландом, заимствуют в своей терминологии многое из естественной генетики. Впервые они были применены к таким научным проблемам, как распознавание образов и оптимизация. ГА представляет собой адаптивный поисковый метод, который основан на селекции лучших элементов в популяции, подобно эволюционной теории Ч. Дарвина.

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

Эволюционный поиск с точки зрения преобразования информации в интеллектуальной ИС -- это последовательное преобразование одного конечного нечеткого множества промежуточных решений в другое. Само преобразование можно назвать алгоритмом поиска, или генетическим алгоритмом.

ГА -- это не просто случайный поиск. Они эффективно используют информацию, накопленную в процессе эволюции. Цель ГА состоит в том, чтобы:

1. абстрактно и формально объяснить адаптацию процессов в ЕС и интеллектуальной ИС;

2. смоделировать естественные эволюционные процессы для эффективного решения оптимизационных задач науки и техники.

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

ГА, согласно, отличаются от других оптимизационных и поисковых процедур следующим:

1. работают в основном не с параметрами задачи, а с закодированным множеством параметров;

2. осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений;

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

4. применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

Для работы ГА выбирают множество натуральных параметров оптимизационной проблемы и кодируют их в последовательность конечной длины в некотором алфавите. ГА работает до тех пор, пока не будет выполнено заданное число генераций (итераций алгоритма) или когда на некоторой генерации будет получено решение определенного качества, или когда найден локальный оптимум, т. е. возникла преждевременная сходимость и невозможно найти выход из этого состояния. В отличие от других методов оптимизации ГА, как правило, анализируют различные области пространства решений одновременно и поэтому они более приспособлены к нахождению новых областей с лучшими значениями ЦФ.

Однако не всегда удается успешно выявить "узкое" место в изобретательской ситуации. Кроме того, таких "узких" мест может быть несколько. Поэтому наряду с направленным методом поиска необходим некоторый перебор вариантов. В этом случае дополнение АРИЗ генетическими алгоритмами поиска представляет собой перспективное и актуальное направление.

Для использования генетического алгоритма необходимо иметь набор некоторых элементов или популяцию, в которой путем селекции отбираются лучшие элементы. Элементы или особи популяции должны иметь математическое описание, пригодное для механизма селекции, при действии которого (механизма) выбираются эти лучшие элементы.

1. Понятия и определения теории генетических алгоритмов

генетический алгоритм изобретательская задача

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р= {р₁, р₂, …,р_i,…,рN_p}есть множество элементов р_i. Здесь N_p-- размер популяции. Каждый элемент этой популяции Р_i,как правило, представляет собой одну или несколько хромосом, или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называются лоци или локус для одной позиции, т. е. ген -- под-элемент (элемент в хромосоме), локус -- позиция в хромосоме, аллель -- значение гена.

Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита {0,1},хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины семь на основе двоичного алфавита может служить хромосома р_i = (0001101).Элементы в ГА часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители создают новую популяцию. Генерация, т. е. процесс реализации одной итерации алгоритма, называется поколением.

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

Каждый элемент в популяции имеет определенный уровень качества, который характеризуется значением ЦФ (в литературе иногда называется функция полезности или пригодности -- fitness). ЦФ используется в ГА для сравнения решений между собой и выбора из них лучших. Основная задача генетических алгоритмов состоит в оптимизации целевой функции. Другими словами, ГА анализирует популяцию хромосом, представляющих комбинацию элементов из некоторого множества, и оптимизирует ЦФ, оценивая каждую хромосому. Генетические алгоритмы манипулируют популяцией хромосом на основе механизма натуральной эволюции.

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

Так же как процесс эволюции начинается с начальной популяции, так и алгоритм начинает свою работу с создания начального множества конкурирующих между собой решений оптимизационной задачи. Затем эти «родительские» решения создают «потомков» путем случайных и направленных изменений. После этого оценивается эффективность решений, и они подвергаются селекции. Как и в ЕС, здесь действует принцип «выживания сильнейших», наименее приспособленные решения «погибают», а затем процесс повторяется вновь.

ГА в зависимости от размера популяции разделяют на:

1. стационарного состояния;

2. поколенческие.

В стационарных ГА размер популяции является входным постоянным параметром, задаваемым ЛПР. В поколенческих ГА разрешается увеличивать или уменьшать размер популяции в каждой последующей генерации. Следует отметить, что речь в основном идет о появлении Np + N₁ потомков (N₁>> 1), прежде чем начинает реализовываться оператор отбора, устраняющий N₁хромосом с меньшей ЦФ. Вопросы удаления «лишних» хромосом, как в стационарных, так и в поколенческих ГА, основаны на нескольких эвристиках:

1. случайное равновероятное удаление хромосом;

2. удаление N₁ хромосом, имеющих худшее значение ЦФ;

3. удаление хромосом на основе обратно пропорционального значения ЦФ;

4. удаление хромосом на основе заданной турнирной стратегии.

Можно предложить еще ряд эвристик удаления, но удаление худших хромосом может привести к преждевременной утрате разнообразия и, следовательно, к попаданию ЦФ в локальный оптимум. Оставление в популяции большого числа хромосом с «плохой» ЦФ приведет к слепому поиску.

Выделяют три особенности алгоритма эволюции:

1. каждая новая популяция состоит только из «жизнеспособных» хромосом;

2. каждая новая популяция «лучше» (в смысле ЦФ) предыдущей;

3. в процессе эволюции последующая популяция зависит только от предыдущей.

Традиционные оптимизационные алгоритмы для нахождения лучшего решения используют большое количество допущений при оценке ЦФ. Эволюционный же подход не требует таких допущений. Это расширяет класс задач, которые можно решать с помощью эволюционного моделирования. Согласно существующим исследованиям можно сказать, что эволюционные методы иГА позволяют решать те проблемы, решение которых традиционными оптимизационными алгоритмами затруднительно.

ГА дает ряд преимуществ при решении практических задач. Одно из таких преимуществ -- это адаптация к изменяющейся окружающей среде. В реальной жизни проблема, которая была поставлена для решения изначально, может претерпеть огромные изменения в процессе своего решения. При использовании традиционных методов все вычисления приходится начинать заново, что приводит к большим затратам машинного времени. При эволюционном подходе популяцией служит БЗ, которую можно анализировать, дополнять и видоизменять применительно к изменяющимся условиям. Для этого не требуется полный перебор. Другое преимущество ЭМ для решения задач состоит в способности быстрой генерации достаточно хороших решений.

При решении практических задач с использованием ЭМ, необходимо выполнить следующие четыре предварительных этапа:

1. выбрать способ представления решения;

2. разработать операторы случайных изменений;

3. определить законы выживания решения;

4. создать начальную популяцию.

Рассмотрим некоторые особенности выполнения этих этапов.

Для представления решения в виде, удобном для реализации на ЭВМ, требуется такая структура, которая позволит кодировать любое возможное решение и производить его оценку. Математически доказано, что не существует идеальной структуры представления, так что для создания хорошей структуры требуется анализ, перебор и эвристические подходы. Возможный вариант представления должен позволять проведение различных перестановок в хромосомах. Необходимо также определить способ вычисления ЦФ для оценки решений.

Достаточно сложным является этап выбора случайного оператора (или операторов) для генерации потомков. Их существует огромное число. В ЕС используются два основных типа размножения: половое ибесполое. При половом размножении два родителя обмениваются генетическим материалом, который используется при создании потомка. Бесполое размножение -- это фактически клонирование, при котором происходят различные мутации припередачи информации от родителя к потомку. Эти операторы очень важны при ЭМ, однако в общем случае для интеллектуальной ИС можно применить и операции, которые не существуют в ЕС. Например, использовать материал от трех или более родителей, проводить голосование при выборе родителей. Фактически нет пределов в использовании различных операторов и нет никого смысла только слепо копировать законы природы и ограничиваться ими.

Успех ЭМ во многом зависит от того, насколько хорошо взаимодействуют между собой схема представления, операторы случайных изменений и способ определения ЦФ. Поэтому для определенного класса задач более целесообразно использовать специальные определенные для этих задач операторы. То же можно сказать и о представлении, так как не существует универсального кодирования, которое можно использовать во всех оптимизационных задачах.

В качестве примера рассмотрим два способа представления перестановок при решении оптимизационных задач. В первом случае будем использовать одного родителя, и получать потомка. Во втором операторе мы используем двух родителей, случайно выберем точку перестановки и для образования потомка возьмем первый сегмент у первого родителя, а второй сегмент -- у второго. Первый оператор похож на бесполое размножение, а второй оператор -- на половое размножение. Стоит отметить, что если первый оператор всегда генерирует реальное решение, то второй может генерировать недопустимые решения. Но это не мешает нам его использовать, просто требуется «восстанавливать» решения перед их оценкой. Например, можно использовать замещение. Как только это сделано для каждого повторяющегося решения, потомок будет восстанавливаться, и будет соответствовать реальному решению.

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

Последний предварительный этап заключается в создании начальной популяции. Если у нас недостаточно знаний о проблеме, то решения могут случайным образом выбираться из всего множества возможных. Это означает генерацию случайных перестановок, где каждая перестановка представляет собой определенное решение. С другой стороны, можно использовать некоторые знания о задаче при создании начальной популяции, например, эти данные могут быть получены из опыта решения этой же задачи другими алгоритмами. Если эти решения действительно ценные, то они выживут и произведут потомство, если же нет, то они погибнут вместе с другими слабыми индивидами[1,5].

2. Математический базис изобретательской физики

Для перехода от физики изобретательских задач к математическим моделям предложено использовать кинематическую систему физических величин Р. Бартини, представленную в таблице1.

Таблица 1 - Кинематическая система величин Бартини

D.	L-1	L0	L1	L2	L3	L4	L5
T-5	L-1T-5	L0T-5	L1T-5	L2T-5	Поверхн. мощность	L4T-5	Мощность
T-4	L-1T-4	L0T-4	Удельный вес Градиент давления	Давление Напряжение	Поверхн. натяжение Жесткость	Сила	Энергия Статистич. температура Момент
T-3	L-1T-3	L0T-3	Плотность потока	Напряженность эл.-магн. поля Вязкость	Ток Массовый расход	Импульс	L5T-3
T-2	Измерение электр. Объемной плотности	Угловое ускорение Массовая плотность	Линейное ускорение	Разность потенциалов	Масса Кол-во электричества	Магнитный момент	Момент инерции
T-1	Электр. Объемная плотность	Частота Угловая скорость	Линейная скорость	Обильность двумерная	Расход объемный	Скорость смещения объема	L5T-1
T0	Кривизна Измерение проводимости	Безразмерная величина Константа	Длина Емкость Само-индукция	Поверхность (площадь)	Объем	Момент инерции плоской фигуры	L5T0
T1	Проводимость	Период Продолжительность	Длительность расстояния	L2T1	L3T1	L4T1	L5T1
T2	L-1T2	Поверхность времени	L1T2	L2T2	L3T2	L4T2	L5T2

Система опирается всего на две базовых единицы, каждая из которых квантуется - единицу длиныL и единицу времени T.Размерности всех остальных физических величин представляются как произведение целочисленных степеней базовых единиц L^mT^-n. Поскольку измерение осуществляется в трехмерном мире, то соотношение степеней размерностей должно подчиняться правилу: |m+n|?3.

Согласно терминологии горизонтальные строки таблицы называются трендами пространственных ресурсов. Легко заметить, что размерности свойств всех элементов тренда имеют в своем составе множитель L⁺¹, который передается по наследству от свойства к свойству слева направо, и который можно назвать геном длины.

Аналогично пространственным трендам можно ввести понятие временных трендов - это столбцы таблицы. В столбцах от свойства к свойству снизу вверх передается ген времени T⁺¹.

Кроме ресурсов пространства и времени, следует определить место вещественно-полевых ресурсов (ВПР) в таблице Бартини. Для этого введем понятие тренда ВПР - это диагональ таблицы, проходящая слева снизу направо вверх. Тренды ВПР образуют семь диагоналей, содержащие физические свойства с размерностями L^mT^-n, при |m+n|?3. Все тренды ВПР от поколения к поколению передают ген скорости L¹T^-1=V⁺¹. Сумма показателей степеней величин, лежащих на отдельном тренде, совпадает и отличается от суммы показателей степеней величин соседних трендов на единицу.

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

генетический алгоритм изобретательская задача

(1)

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

Когда инерция преодолена, свойство икс-элемента четко фиксируется сознанием, т.е. уже не изменяется, наступает установившийся режим , и из дифференциального уравнения получаем алгебраическое уравнение:

(2)

Произведение передает наследственную информацию о свойствах и "родителей", свойству их "ребенка", то есть икс-элементу. Для определения физического свойства переходим от математического уравнения к его физического эквиваленту в виде уравнения размерностей в LT-базисе Бартини:

L^m3Tⁿ³= C· L^m1Tⁿ¹ ·L^m2Tⁿ² (3)

ПостояннаяC является размерной константой, т.е. L^m4Tⁿ⁴, и где все m_i и n_j - целые числа, положительные и отрицательные.

В уравнении произведение L^m1Tⁿ¹ ·L^m2Tⁿ² определяет тот элемент тренда ВПР, в котором заложены свойства того и другого "родителей". Сам же тренд ВПР, проходящий через этот элемент с размерностью L^m1Tⁿ¹ ·L^m2Tⁿ², может быть назван родительским.

Следовательно, операцией скрещивания особей будет умножение соответствующих физических размерностей. Однако если традиционно рассматривается одно, ключевое, противоречие, то в генетическом алгоритме их участвует десятки и сотни, что позволяет вовлечь в процесс решения множество факторов и ресурсов, имеющихся в задаче[2].

3. Генетический алгоритм в изобретательской задаче

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

1. Описание изобретательской ситуации

2. Синтез потоковой информационно-энергетической структурной схемы

3. Выбор факторов системы, влияющих на потребительские характеристики задачи.

4. Кодирование факторов с помощью LT-таблицы Бартини.

5. Создание исходной популяции факторов.

6. Расчет функций приспособленности факторов.

7. Проверка условия завершения генетического алгоритма.

Если условие не достигнуто, то продолжается селекция факторов, скрещивание и мутация, а затем создание новой популяции.

Если условие достигнуто, то выбирается лучший фактор для решения задачи и выход из алгоритма.

8. Переход к шагу 6.

Генетический алгоритм начинается с шага 4 - кодирования факторов. Кодирование факторов означает, что особям (факторам) присваиваются физические размерности из таблицы Бартини. Кроме того, для каждой особи должна рассчитываться функция приспособленности, позволяющая определить, какая физическая размерность более или менее подходит для решения поставленной задачи. Функцию приспособленности выбираем исходя из условия конкретной задачи. Для принятия решения рассчитаем родительский тренд, и по таблице Бартини найдем с помощью генетического алгоритма ту физическую размерность, которая находится на родительском тренде и имеет наибольшую среди особей этого тренда функцию приспособленности.

3.1 Операторы генетических алгоритмов

В каждой генерации хромосомы являются результатом применения некоторых генетических операторов. В простых ГА (ПГА) Д. Гольдберга существует три основных оператора (или функции, или шага, или процесса): селекция (репродукция), кроссинговер (скрещивание) и мутация.

Рассмотрим кратко эти основные операторы. Натуральная селекция -- это процесс, посредством которого хромосомы, имеющие более высокое значение ЦФ (с сильными признаками), получают большую возможность для репродукции, чем слабые хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичные или различные потомки.

Существует много различных видов селекции,рассмотрим основные из них.

Селекция на основе рулетки -- это самый простой и наиболее используемый в ПГА метод. При его использовании каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции, причем элемент с большим значением ЦФ имеет большую вероятность для выбора.

Селекция на основе заданной шкалы. Здесь популяция предварительно сортируется от «лучшей» особи к «худшей» на основе заданного критерия. Каждому элементу назначается определенное число и далее селекция выполняется согласно этому числу.

Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения ЦФ. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс идет до тех пор, пока продолжают появляться элитные элементы.

Турнирная селекция. При этом некоторое число элементов (согласно размеру «турнира») выбирается случайно или направленно из популяции, и лучшие элементы в этой группе на основе заданного турнира определяются для дальнейшего генетического поиска.

Кроме описанных, существует большое число других методов селекции, которые можно условно классифицировать на три группы. К первой группе отнесем вероятностные методы селекции. Ко второй -- детерминированные. К третьей -- различные комбинации методов из первой и второй групп. Поиски оптимальных методов селекции непрерывно продолжаются. Дело в том, что основной трудностью решения оптимизационных задач с большим количеством локальных оптимумов является предварительная сходимость алгоритмов. Другими словами, происходит попадание решения в один, далеко не самый лучший, локальный оптимум. Различные методы селекции и их модификации как раз и позволяют в некоторых случаях решать проблему предварительной сходимости алгоритмов. Следует отметить, что исследователи ГА все более склоняются к мысли применять комбинированные методы селекции с использованием предварительных знаний о решаемых задачах и предварительных результатах.

Опишем теперь методы кроссинговера. В литературе часто их называют операторами кроссинговера (ОК). Основная функция ОК -- создавать хромосомы потомков на основе различного скрещивания родителей. Существует огромное число ОК, так как их структура в основном и определяет эффективность ГА. Кратко рассмотрим основные ОК, известные в литературе, и их модификации.

Одноточечный (простой) ОК. Перед началом работы одноточечного ОК определяется так называемая точка ОК, или разрезающая точка, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны». Например, пусть популяция Р состоит из двух хромосом Р={р₁, р₂}, которые выступают в качестве родителей. Пусть первый и второй родители имеют вид р₁: (11111), р₂: (00000). Выберем точку ОК между вторым и третьим генами в р₁, р₂. Тогда, меняя элементы после или перед точкой ОК между двумя родителями, можно создать два новых потомка. В нашем примере получим:

Рисунок 1 - Одноточечный ОК

Итак, одноточечный ОК в интеллектуальной ИС выполняется в три этапа:

1. Две хромосомы А = a₁, а₂,..., a_L и В = а'₁, а'₂,..., а'_L выбираются случайно из текущей популяции.

2. Число к выбирается из {1, 2,...,L-1} также случайно. Здесь L -- длина хромосомы, к-точка ОК (номер или значение, код гена, после которого выполняется разрез хромосомы).

3. Две новые хромосомы формируются из А и В путем перестановок элементов согласно правилу

А' = a₁, a₂, … , a_k,a'_k+1,…, a'_L (4)

B' = a'₁, a'₂, … , a'_k,a_k+1,…, a_L (5)

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

В двухточечном ОК определяются две точки ОК, и гены обмениваются между ними. Например:



Рисунок 2 - Двухточечный ОК

Отметим, что точки ОК в двухточечном ОК также определяются случайно. Существует много модификаций двухточечного ОК.

Развитием двухточечного ОК является многоточечный ОК или N-точечный ОК, он выполняется аналогично двухточечному ОК, хотя большое число «разрезающих» точек может привести к потере «хороших» родительских свойств.

Порядковый ОК. В порядковом ОК «разрезающая» точка также выбирается случайно. Далее происходит копирование левого сегмента р₁ в р'₁. Остальные позиции в р'₁ берутся из р₂ в упорядоченном виде слева направо, исключая элементы, уже попавшие в р'₁. Например:

Рисунок 3 - Порядковый ОК

Получение р'₂ может выполняться различными способами. Наиболее распространенный метод -- копирование левого сегмента из р₂, а далее анализ р₁ методом, указанным выше. Тогда имеем р'₂ : (G А В Е | С D F Н).

Частично-соответствующий ОК. Здесь также случайно выбирается «разрезающая» точка или точка ОК. Дальше анализируются сегменты в обоих родителях, и устанавливается частичное соответствие между элементами первого и второго родителей с формированием потомков. При этом правый сегмент р₂ переносится в р'_1, левый сегмент р₁ переносится в р'₁ с заменой повторяющихся генов на отсутствующие (гены, находящиеся в частичном соответствие). Например:

Рисунок 4 - Частично-соответствующийОК

Циклический ОК. Циклический OK выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция Р состоит из двух хромосом Р = {р_1,р₂}. Первый и второй родители и их потомок имеют вид:

Рисунок 5 - Циклический ОК

Универсальный ОК. В настоящее время он популярен для решения различных задач теории расписаний. Вместо использования разрезающей точки (точек) здесь определяют двоичную маску, длина которой равна длине заданных хромосом. Получение потомков выполняется на основе правил сложения булевой алгебры соответствующих генов родителей и маски (0 + 0 = 0, 0 + 1 = 1, 1 + 1=0). Для каждого элемента в p₁, р₂ гены меняются, как показано на следующем примере:



Рисунок 6 - Универсальный ОК

Маска обычно выбирается случайно с заданной вероятностью или на основе генератора случайных чисел. При этом чередование 0 и 1 в маске происходит с вероятностью «0,5 (т. е. приблизительно в 50% случаев). В некоторых случаях используются параметризированный универсальный ОК, где маска может выбираться с вероятностью для 1 или 0 выше, чем 0,5. Такой вид маски эффективен, когда хромосомы кодируются в двоичном алфавите.

В оптимизационных задачах находят применение различного типа «жадные» операторы кроссинговера. Они основаны на анализе ЦФ решений после каждого шага «жадного» ОК. Он может быть реализован на двух и более хромосомах, а в пределе -- на всей популяции. Приведем типичный модифицированный алгоритм «жадного» ОК:

1. Для всех хромосом популяции вычисляется ЦФ. Выбирается заданное число родительских хромосом, и случайным образом на одной из хромосом определяется точка «жадного» ОК.

2. В выбранной хромосоме для i-го гена, расположенного слева от точки «жадного» ОК, определяется частичная ЦФ, т. е. стоимость пути от i-гo гена к рядом находящемуся гену. Аналогичные действия выполняются по определению стоимости пути во всех остальных хромосомах, выбранных для «жадного» ОК.

3. В хромосому «потомок» выбирают тот ген, у которого значение ЦФ выше (ниже) при максимизации (минимизации) ЦФ.

4. Процесс продолжается, пока не будет построена хромосома «потомок». Если в процессе реализации «жадного» О К возникает цикл или тупик, то в потомок выбираются нерассмотренные гены с лучшей ЦФ.

Например, пусть популяция Р состоит из трех родительских хромосом Р = {р₁, р_2, р₃}, где p₁:(abcde); p₂:(bdeca); p₃:(ebadc). Причем «стоимость» (ЦФ) для каждого гена в хромосоме задана матрицей:

Рисунок 7 - Матрица «стоимости» ген в хромосоме

Согласно алгоритму выберем точку «жадного» ОК между генами b и с в хромосоме p₁. Теперь выбор (b-c) дает значение ЦФ, равное 4; выбор (b-а) определяет ЦФ со значением 15, а выбор (b-d) определяет ЦФ, равную 3. При решении задачи минимизации ЦФ выберем путь (b-d). Продолжая далее, получим путь реализации «жадного» ОК. Итак, хромосома потомка р': (b d с а е) имеет суммарную ЦФ, равную 18 (3 +1 + 6 + 8 = 18), а ЦФ родителей для p₁ равна 15 + 4 + 1 + 9 = 29, для р₂ равна 3 + 9 + 10 + + 6 = 28 и для р₃ равна 2 + 15 + 7 + 1 = 25. Стратегию «жадного» ОК можно выполнять различными способами.

Следует отметить, что исследователи продолжают поиск оптимального ОК.

Рисунок 8 - Поиск оптимального ОК

Рассмотрим кратко основные операторы мутации (ОМ). Мутация необходима потому, что предотвращает потерю важного генетического материала. Обычно ОМ является одноточечным оператором, который случайно выбирает ген в хромосоме и обменивает его на рядом расположенный ген. Например, одноточечный ОМ имеет вид:

Рисунок 9 - Одноточечный ОМ

Двухточечный ОМ заключается в перестановке генов, расположенных справа от точек разрыва. Например:

Рисунок 10 - Двухточечный ОМ

Процесс преобразования в ЕС и ИС обычно происходит толчками. При этом важную роль играют толчковые мутации. Они не изменяют размера и строения хромосом, а изменяют взаимное расположение генов в хромосоме.

В оптимизационных задачах, с нашей точки зрения, интерес может представлять использование ОМ, основанных на знаниях о решаемой задачи.Такие ОМ называются «аргументированными знаниями». В них могут переставляться местами любые выбранные гены в хромосоме. Как правило, втаких ОМ точка или точки мутации определяются не случайно, а направленно. Например, в позиционном операторе мутации две точки мутации выбираются случайно, а затем ген, соответствующий второй точке мутации, размещается в позицию перед геном, соответствующим первой точке мутации. Например:



Рисунок 11 - Пример

Согласно Д. Холланду, ОМ выполняется следующим образом:

1. В хромосоме А = (a₁, a₂, a₃,..., a_L-2, a_L-1, a_L) определяются случайным образом две позиции (например, а₂ и a_L-1).

2. Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома. ОМ -- А' = (a₁, a₂, a₃,..., a_L-2, a_L-1, a_L).

Заметим, что в ПГА ОК -- бинарная операция, а ОМ -- унарная операция. Кроме того, ОК и ОМ соответствуют перестановкам элементов внутри заданного множества. Важным понятием в ОМ является шкала мутации, которая определяет, какой процент общего числа генов в популяции видоизменяется в каждой генерации. Для оптимизационных задач вероятность ОК обычно принимают равной 0,6?0,99. а вероятность ОМ от 0,6 и меньше.

Кроме мутации, популярным и используемым в ЕС и ИС является оператор инверсии. В операторе инверсии случайным образом определяется одна или несколько точек инверсии, внутри которых элементы инвертируются.

Генетический оператор инверсии в ГА Д. Холланда состоит из следующих шагов:

1. Хромосома В = (b₁, b₂, ..., b_L) выбирается случайным образом из текущей популяции.

2. Два числа у'₁ и у'₂ выбираются случайным образом из множества {0, 1, 2, ..., L+1}, далее определяем у₁ = min{ у'_1, у'₂} и у₂ = max{ у'_1, у'₂}.

3. Новая хромосома формируется из В путем инверсии сегмента, который лежит справа от позиции у₁ и слева от позиции у₂ в хромосоме В.

Тогда, после применения оператора инверсии, получаем B_{1 :}B₁=(b₁,…, b_y1, b_y2-1, b_y2-2,…, b_y1+1, b_y2,…, b_L)

Например, для двухточечного оператора инверсии получим:

Рисунок 12 - Двухточечный ОИ

Для одноточечного оператора инверсии запишем:

Рисунок 13 - Одноточечный ОИ

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

Рассмотрим оператор транслокации. Он представляет собой комбинацию ОК и оператора инверсии. В процессе транслокации случайным образом производится один разрыв в каждой хромосоме. При формировании потомка p'₁ берется левая часть до разрыва из родителя p₁ и инверсия правой части до разрыва из р₂. При создании p'₂ берется левая часть р₂ и инверсия правой части р₁. Приведем пример оператора транслокации:

Рисунок 14 - Оператор транслокации

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

Кроме описанных операторов, по мнению авторов, интерес может представлять оператор сегрегации и различные его модификации. Приведем один из примеров реализации оператора сегрегации. Отметим, что оператор сегрегации, как правило, реализуется на некотором наборе хромосом. Пусть имеется популяция Р, состоящая из четырех родительских хромосомР = {р₁, р₂, р_3, р₄}: р₁: (1234); р₂: (2431); р₃: (3142); р₄: (4321). Тогда потомок p'₁ можно сформировать случайным образом, взяв первый элемент (один или несколько генов) из p₁, второй из р₂, третий из р₃ и четвертый из р₄. При этом должны быть отброшены повторяющиеся решения, или решения, содержащие одинаковые элементы. Так, вариант p'₁: (1412) должен быть отброшен как содержащий две единицы, а вариант p'₂: (2143) является легальным (допустимым или реальным). Очевидно, что оператор сегрегации можно реализовать различными способами в зависимости от способа выбора генов из хромосом.

Опишем оператор удаления. При реализации оператора удаления направленным или случайным образом определяется точка или точки оператора удаления. Далее производится пробное удаление генов или их ансамблей с вычислением изменения ЦФ. При достижении экстремума ЦФ оператор удаления реализуется. Элементы, расположенные справа от точки оператора удаления или между двумя точками оператора удаления, удаляются из хромосомы.

Опишем оператор вставки. При реализации оператора вставки направленным или случайным образом определяется точка или точки оператора вставки. Затем анализируются другие гены хромосом в популяции для определения альтернативных вставок. Далее производится пробная вставка генов или их.ансамблей с вычислением изменения ЦФ. При достижении экстремума ЦФ оператор вставки реализуется. Новые гены или их ансамбли вставляются, в хромосому справа от точки оператора вставки или между его двумя, точками. Отметим, что оператор удаления и оператор вставки меняют размер хромосом. Для сохранения размера хромосом постоянным эти операторы необходимо применять совместно.

Рассмотрим теперь понятие рекомбинации. Функция рекомбинации определяет, как новая, генерация хромосом будет построена из родителей и потомков. Другими словами, функция рекомбинации -- это анализ и преобразование популяции при переходе из одной генерации в другую. Существует много путей выполнения рекомбинации. Один из них состоит из перемещения родителей в потомки после каждого генетического оператора (ГО). Другой путь заключается в перемещении некоторого процента популяции, используя потомков в течение каждой генерации. Обычно в ГА задается параметр W(P), который управляет этим процессом. Так, N_P(1 -- W(P)) элементов в популяции Р, выбранных случайно, могут «выжить» в следующей генерации. Здесь N_P -- размер популяции. Величина W (Р) = 1 означает, что целая предыдущая популяция перемещается в новую в каждой генерации. При дальнейшей реализации алгоритма лучшие элементы из родителей и потомков будут выбираться, для формирования новой популяции[5,6].

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

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

1. Конструирование начальной популяции. Ввести точку отчета поколений t = 0. Вычислить приспособленность хромосом популяции, а затем среднюю приспособленность популяции.

2. Установление t = t + 1. Выбрать двух родителей (хромосом) для кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формирование генотипа потомка. С заданной вероятностью произвести над генотипами выбранных хромосом кроссинговер. Выбрать с вероятностью 0,5 один из потомков p(t) и сохранить его как члена новой популяции. Последовательно применить к р(t) оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохранить как p'(t).

4. Отбор хромосомы случайным образом для исключения ее из популяции. Обновление текущей популяции заменой отобранной хромосомы на p'(t).

5. Определение приспособленности (целевой функции) p'(t) и пересчет средней приспособленности популяции.

6. ЕСЛИ t = t_{заданному}, то переход к 7, если нет, то переход к 2.

7. Конец работы.

Мы привели так называемый репродуктивный план Д. Холланда в несколько упрощенном виде. Заметим, что в технических задачах оптимизации часто вместо понятия «приспособленность» используют понятие «целевая функция». Биологи называют эту функцию -- fitnessfunction. Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Он копирует последовательности и переставляет их части. Предварительно ПГА случайно генерирует популяцию последовательностей -- хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем он применяет множество простых операций к начальной популяции и генерирует новые популяции.

ПГА состоит из трех операторов:

* репродукции;

* кроссинговера (ОК);

* мутации (ОМ).

3.3 Пример

Рассмотрим классическую изобретательскую задачу о запайке ампулы с лекарством. Имеется ампула с жидким лекарством, которая установлена вертикально капилляром вверх и движется по транспортеру в кассете с другими ампулами. В определенном месте транспортер останавливается, к капиллярам ампул придвигаются газовые горелки, капилляры оплавляются и герметизируют ампулу (рисунок 15). Здесь можно сформулировать техническое противоречие: если длина пламени большая, тогда запайка хорошая, но место лекарство перегревается и портится, если длина пламени маленькая, тогда запайка плохая, но лекарство не портится. Цель задачи - найти некий ресурс - икс-элемент, который позволит разрешить это противоречие и обеспечит как хорошую запайку ампулы, так и сохранность лекарства.

Рисунок 15 - Запайка ампул с лекарством

Составим структурную потоковую схему преобразования энергии и информации (рисунок 16).



Рисунок 16 - Потоковая структурная схема

По схеме определяем, какие вещества и поля следует учитывать при решении задачи, а затем, - какие ресурсы (факторы) выбрать для описания этих веществ и полей. Чем больше факторов мы выберем, тем больше информации о задаче получит алгоритм поиска, и тем эффективнее он будет работать. В этом отличие генетического алгоритма от АРИЗ. АРИЗ строит модель задачи в виде противоречия для одного, «узкого» места структуры. Например, в рассматриваемой задаче «узкое» место - это пара пламя-ампула (лекарство), все остальные вещества и поля с их свойствами исключаются из модели. Хорошая запайка оценивается длиной оплавленной части капилляра, а порча лекарства - температурой пламени. Скрещивание двух факторов - длины и температуры дает лишь один родительский тренд.

Использование же генетического алгоритма позволяет использовать структурную модель более широко, предположив в ней наличие многих противоречий в виде бинарных отношений свойств веществ и полей. Благодаря этому появляется несколько родительских трендов. Если скрещивание выводит особь на нереализуемый в трехмерном пространстве тренд, то она (особь) скрещивается с третьим фактором, возвращающим потомка на реализуемый тренд, т.е. в этом случае используются уже тернарные отношения между свойствами.

Выберем следующие факторы, разнородно влияющие на качество запайки ампулы:

1. температура пламени;

2. температура лекарства;

3. давление в горелке;

4. объем ампулы;

5. длина (высота) ампулы;

6. длина капилляра ампулы;

7. длина (диаметр) сопла горелки;

8. длина (толщина) стенок ампулы:

9. теплоемкость стекла;

10. время запайки.

Теперь эти факторы мы должны скрестить. Для этого разобьем факторы попарно и логически перемножим их физические размерности по формуле(3). Результат приведен в таблице 2.

Таблица 2 - Факторы, влияющие на запайку ампулы

Входной фактор, х	Входной фактор, y	Выход, z	Сумма показателей степеней m+n
Длина, L1T0	Длина, L1T0	L2T0	2
Длина, L1T0	Время, L0T1	L1T1	2
Время, L0T1	Время, L0T1	L0T2	2
Время, L0T1	Температура, L5T-4	L5T-3	2
Длина, L1T0	Температура, L5T-4	L6T-4	2
Температура, L5T-4	Температура, L5T-4	L10T-8	2
Давление, L2T-4	Теплоемкость, L0T-2	L2T-6	-4
Объем, L3T0	Длина, L1T0	L4T0	4

Расчет показал, что родительский тренд для задачи о запайке ампул задается показателем m+n=2. Кроме того, имеются и другие родительские тренды, полученные перемножением других факторов. Следовательно, в задаче действует целый ряд противоречий, которые можно использовать для нахождения другого решения. Далее нам следует определить, какой из ресурсов на родительском тренде может дать наиболее эффективное решение задачи. Для поиска решения воспользуемся генетическим алгоритмом.

На первом шаге производится инициализация, или выбор исходной популяции особей (таблица 3, второй столбец). В нашей задаче особями являются физические размерности таблицы Бартини (таблица 1). Нам предстоит в ходе искусственной эволюции выбрать среди них наилучшую с точки зрения решения поставленной задачи. Необходимо определить функцию приспособленности каждой особи (таблица 3, третий столбец). Для этого присвоим каждой из них некоторую «ценность», выраженную числом в диапазоне от единицы до пяти. Чем больше число, тем более приспособленной является особь. Факторы, непосредственно влияющие на запайку ампулы, обладают наиболее «сильной» наследственной информацией, поэтому их надо поощрить - придадим им максимальную «ценность» - пять баллов. Остальные ресурсы пока не несут какой-либо наследственной информации - поэтому оценим их единицей. Анализироваться будут только те величины, которые в таблице имеют физическое определение.

Таблица 3 - Исходнаяпопуляцияособей

Номер особи	Особь	Функция приспособленности	Сектор	Границы секторов
1	L3T-5	1	1,72	1,72
2	L5T-5	1	1,72	3,45
3	L1T-4	1	1,72	5,17
4	L2T-4	5	8,62	13,79
5	L3T-4	1	1,72	15,52
6	L4T-4	1	1,72	17,24
7	L5T-4	5	8,62	25,86
8	L1T-3	1	1,72	27,59
9	L2T-3	1	1,72	29,31
10	L3T-3	1	1,72	31,03
11	L4T-3	1	1,72	32,76
12	L-1T-2	1	1,72	34,48
13	L0T-2	5	8,62	43,10
14	L1T-2	1	1,72	44,83
15	L2T-2	1	1,72	46,55
16	L3T-2	1	1,72	48,28
17	L4T-2	1	1,72	50,00
18	L5T-2	1	1,72	51,72
19	L-1T-1	1	1,72	53,45
20	L0T-1	1	1,72	55,17
21	L1T-1	1	1,72	56,90
22	L2T-1	1	1,72	58,62
23	L3T-1	1	1,72	60,34
24	L4T-1	1	1,72	62,07
25	L-1T0	1	1,72	63,79
26	L0T0	1	1,72	65,52
27	L1T0	5	8,62	74,14
28	L2T0	1	1,72	75,86
29	L3T0	5	8,62	84,48
30	L4T0	1	1,72	86,21
31	L-1T1	1	1,72	87,93
32	L0T1	5	8,62	96,55
33	L1T1	1	1,72	98,28
34	L0T2	1	1,72	100,00

Далее проверяется условие остановки алгоритма. Примем, что для нашего примера поиска необходимо сделать 5 итераций. Поскольку для исходной популяции ни одного шага алгоритм еще не сделал, то условие остановки не выполнено. Тогда на следующем этапе необходимо провести селекцию особей для скрещивания. Селекция заключается в выборе (по рассчитанным на предыдущем этапе значениям функции приспособленности) тех особей, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют особи с наибольшими значениями функции приспособленности.

Рисунок 17 - Сектора рулетки для всех особей исходной популяции

В задаче для селекции был использован метод рулетки. Каждой особи может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной особи (рисунок 17). Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки.

Все колесо рулетки соответствует сумме значений функции приспособленности всех особей. Каждой особи, обозначаемой ch_i для i=1,2,…N (где Nобозначает численность популяции), соответствует сектор колеса н(ch_i), выраженный в процентах согласно формуле:

(6)

(7)

причем- значение функции приспособленности особи -, а- вероятность селекции особи .

Селекция особи может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая», т.е. выбранная особь относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей особи. Поэтому вероятность выбора данной особи оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор особи можно отождествить с выбором числа из интервала [а, b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору коле­са; очевидно, что0< а < b < 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса.

Согласно описанному методу для каждой особи текущей популяции (в нашем случае - исходной популяции) получаем секторы колеса рулетки, выраженные в процентах (таблица 3, четвертый столбец). Приведем пример расчета сектора колеса рулетки н(ch₁)для первой особи популяции L³T^-5. Вычислим сумму функций приспособленности всех особей популяции: