Перспективы развития систем искусственного интеллекта

Перспективы развития систем искусственного интеллекта

Рассматриваются два основных направления искусственного интеллекта:

1. Заключается в решении проблем связанных к приближениям специализированных систем искусственного интеллекта к возможностям человека.

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

 

Различные подходы построения систем искусственного интеллекта

Существует 4 основных подхода:

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

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

2. Структурный подход – это попытка моделирования структуры человеческого мозга. Одной из таких попыток было устройство персептрон. Основной моделируемой структурной единицей персептрона, как и в большинстве других вариантов моделирования мозга является нейрон. Позднее возникли и другие модели, которые носят название нейронные сети. Эти модели различаются по строению отдельных нейронов по топологии связи между ними и по алгоритмам обучения. Среди наиболее известных нейроновых сетей можно назвать сети с прямым и обратным распространением ошибки стохастические нейронные сети Хопфилда. Нейронные сети наиболее успешно применяются в распознавании образа, а также в задачах прогнозирования, экспертных системах и т.д. Для структурных моделей характерно не слишком большая выразительность, небольшое распараллеливание алгоритмов и связанная с этим высокая производительность. Одним из самых важных свойств модели – это способность работы при условии не полной информации.

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

4. Имитационный подход – данный подход является классическим для кибернетики, в его реализацию часто используют устройство, которое называется «Черный ящик».

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

Основным недостатком имитационного подхода является низкая информационная способность большинства моделей.

 

 

Логический подход

В логическом подходе оперирует название неформальной процедуры. Неформальные процедуры – это один из способов приблизиться к человеческому способу представлению человеком функции.

Пример:

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

Дом, мама, вилка, кино, ночь, токарь, киль.

 

 

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

Введем дополнительную задачу.

Расширить предыдущий алгоритм на 4 слова: Задача, акция, время, Вася.

Ситуация	Действие	Ситуация	Действие
КИНО	КИНО	-Ь	-И
-ча	-чи	-ие	-ия
-КА	-КИ	-мя	-мени
-А	-Ы	-я	-и
-АРЬ	-АРЯ	-	-А
-Ь & М:хЬ	-Я

 

 

В таблице решений слева приведена ситуация (условие), а справа соответственно действие, если условие выполняется.

Теперь значительно упрощается расширение на новые классы слов - необходимо лишь обеспечить внесение вставок на нужное место в таблице решений.

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

"Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" - это набор инструкций, подлежащих выполнению в случае применимости продукции.

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

а.) МАТЬ                               ЛЮБИТ                                 ?

                                                                

                                                      

б.) МАТЬ                               ЛЮБИТ                                ?

 

Лингвистический разбор предложения начинается со слов «мать любит», проанализировав эти слова в первоначальном предложении именительного падежа для слова «мать» система в праве построить структуру в случае а.

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

 

Логический вывод

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

ДЕД, РОДИТЕЛЬ, ВНУК

1.) x – ДЕД – y если x – ОТЕЦ a и a – РОДИТЕЛЬ y

2.) x – РОДИТЕЛЬ y если x – ОТЕЦ y или x – МАТЬ y

3.) x – ВНУК y если y – ДЕД  x

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

Практически при программировании неформальных процедур подобные таблицы можно вручную создавать и сопровождать максимально до 100-200 продукций.

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

Взвешивание свидетельств

Была разработана формула, по которой новые события можно сочетать со старыми результатами:

МД [h,e₁,e₂] = МД [h, e₁] + МД [h, e₂]*(1 – МД [h, e₁])

e_1, e₂ – последовательно поступающиеся свидетельства, свидетельствующие за гипотезу h

Эта формула имеет два важных свойства:

1. Формула симметрична в том смысле, что порядок e₁, e₂  не существенный.

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

Результирующая мера недоверия считается по аналогичной формуле:

МНД [h, e₁, e₂] = МНД [h, e₁] + МНД [h, e₂] * (1 - МНД [h, e₁])

Пример:

Правило 1.

Если у объекта Х высокая температура и у объекта Х покраснение горла, то у него ОРЗ.

Правило 2.

Если у объекта Х насморк или у объекта Х головная боль, то у объекта Х ОРЗ.

1а – 0,8   0,75

1б – 0,75     

   2а – 0,4

2б – 0,6  0,6

Какая результирующая МД соответствует этим двум правилам?

МД [h, e₁, e₂] = 0,75 +0,6 * (1 – 0,75) = 0,9

 

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

Правило 1: ЕСЛИ х

                И х

                    ТО х – ОРЗ

 

Правило 2: ЕСЛИ х

                ИЛИ х

                    ТО х – ОРЗ

 

1а – 0,88 0,5

1б – 0,5       

2а – 0,5

2б – 0,7  0,7

                              

 

Полученные меры доверия 0,5 и 0,7 необходимо умножить на ослабляющие коэффициенты 0,64 и 0,8:

0,5*0,64 = 0,32

0,7*0,8 = 0,56

Затем применяем формулу:

МД [h, e₁, e₂] = 0,32 + 0,56 (1 – 0,32) = 0,7008

 

Байесовский подход

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

ОП (Н:Е) = Р (Е: Н) / Р (Е: Н'),

где ОП – отношение правдоподобия

    Е – свидетельство

    Н – гипотеза

    Р (Е: Н) – вероятность свидетельства Е (или события Е), при условии заданной гипотезы Н.

   Р (Е: Н') – вероятность этого же свидетельства, при условии ложности данной гипотезы.

   Например, если мы знаем вероятность появления сыпи у больных ветряной оспы и вероятность появления другими заболеваниями, то мы можем вычислить заболевания ветряной оспы, если появилась сыпь.

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

   О = Р / (1 - Р)

   Р = О / (1+0),

где О – шансы в пользу чего-либо

   Р - вероятность

Преобразование оценки «шансы против А» в оценку «шансы за А» производится по следующей формуле                                                 

О = 1 / А

Например, 7 против 4 может быть выражено как 1,75 против 1, что соответствует 0,5714 к 1 «за» (или 4 к 7 в пользу рассматриваемой гипотезы).

Байесовская схема уточнения может быть сведена к следующему выражению:

О' (Н) = О (Н)*(Н:Е),

где О(Н) – априорные шансы в пользу гипотезы Н

  О' (Н) – результирующие апостериорные шансы, при условии наступления события Е в соответствии с отношением правдоподобия.

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

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

 

Таблица 1.1

Отношение к курению	Продолжительность жизни		Всего
	> 75 лет	75 лет или меньше
Курящие (чел) Некурящие (чел)	20 24	33 23	53 47
ВСЕГО	44	56	100

 

В приведенной таблице содержатся данные по 100 умершим людям, из которых 44 прожили 75 и больше, и 56 человек не дожили до 75 лет. Причем указано кто из них был курильщиком, а кто нет.

Априорные шансы в этой выборки из 100 случаев в пользу того, что человек проживет более 75 лет, высчитывается по следующей формуле:

О (Долгожитель) = 44 / 56 = 11 / 14 = 0,7857

Отношение правдоподобия считается по следующей формуле:

ОП (Долгожитель:Курящий) = (20/44)/(33/56) = (20*56)/(44*33) = =320/363 = 0,8815

ОП (Долгожитель:Некурящий) = (22/44)/(23/56) = (24*56)/(44*23) = =336/253 = 1,3280

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

                                                                                      

Таблица 1.2

Пол	Продолжительность жизни		Всего
	> 75 лет	75 лет или меньше
Женщина Мужчина	20 24	20 36	40 60
ВСЕГО	44	56	100

 

ОП (Долгожитель:Женщина) = (20/24)/(20/56) =1,2727

ОП (Долгожитель:Мужчина) = (24/44)/(36/56) =0,8484

Учитывая, что априорные шансы в пользу продолжительной жизни равны 11/14 мы можем вычислить апостериорные шансы, что курящий мужчина проживет больше 75 лет пользуясь следующим выражением:

О'(Долгожитель) =ОП(Долгожитель:Курильщик)*

*ОП(Долгожитель:Мужчина)*(Долгожитель)

  О'(Долгожитель) = 0,8815*0,8484*11/14 = 0,5867

Вероятность вычисляется:

Р = О/(1+0) = 0,5867/(1,5867) = 0,3701

Начальная вероятность была равна 0,44.

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

ОП' = ОП +ВС + (1 - ВС),

где ВС - вероятность того, что свидетельство надежно.

Например, если свидетельство известно с вероятностью Р=0,8, то ОП=1,2 в пользу гипотезы уменьшается до ОП' = 1,2 + 0,8 + (1 - 0,8) = 1,2*0,8 + 0,2=

= 0,96 + 0,2 = 1,16.

Например, ОП=0,5 (значительно противоречащее гипотезе) увеличится при использовании этой формулы: ОП' = 0,5*0,5 + 0,5 = 0,75.

Отношения правдоподобия имеют два преимущества:

1) Допускают комбинирования нескольких источников данных

2) Их легко корректировать, если свидетельство не надежно само по себе.

 

Нечеткая логика

Fuzzy logic

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

1) Применение точных методов невозможно

2) Применение точных методов связано с большими затратами времени и ресурсов и имеет смысл пожертвовать точностью вычислений для экономии времени.

3) Нет возможности набрать статистический материал, чтобы воспользоваться теорией вероятности.

Рассмотрим пример, связанный с возрастом человека (рис.1).

До 16 лет нельзя однозначно утверждать, что человек молодой (например, 15-летие относится к термину молодой с рангом около 0,9). Зато диапазону от 16 до 30 лет можно смело присвоить ранг 1, т.е. человек в этом возрасте молодой. После 30 лет человек вроде уже не молодой, но еще и не старый, здесь принадлежность (ранг) термина молодой возрасту будет принимать значения в интервале от 0 до 1. И чем больше возраст человека, тем меньше становится его принадлежность к молодым, т.е. ранг будет стремиться к 0.

Нечеткое множество для термина молодой может быть изображено на следующей диаграмме:

Рис.1. Нечеткое множество для термина молодой

 

К нечетким множествам можно применять следующее операции:

1. Объединение:

 

2. Пересечение:

 

 

3. Дополнение:

 

 

4. Концентрация:

 

 

5. Размывание (размытие):

 

 

6. Фаззификация – это сопоставление множества значений х ее функции принадлежности М (х), т.е. перевод значений х в нечеткий формат.

Дефаззификация – процесс обратный фазификации, т.е. перевод нечетких значений в абсолютные значения х.

В нечеткой логике вводится понятие лингвистической переменной, значениями которого являются не числа, а слова естественного языка, называемыми термами. Например, в случае управления мобильным роботом можно ввести две лингвистические переменные ДИСТАНЦИЯ (расстояние до помехи) и НАПРАВЛЕНИЕ (угол между продольной осью робота и направлением на помеху).

Рассмотрим лингвистическую переменную ДИСТАНЦИЯ. Для нее можно определить следующие термы: ДАЛЕКО, СРЕДНЯЯ, БЛИЗКО, ОЧЕНЬ БЛИЗКО. Для физической реализации лингвистической переменной необходимо определить точные физические значения термов этой переменной.

Пусть переменная ДИСТАНЦИЯ может принимать любое значение из диапазона от 0 до ∞. Согласно положению теории нечетких множеств,  в этом случае каждому значению расстояние из указанного диапазона может быть поставлено в соответствие некоторое число от 0 до 1, которое определяет степень принадлежности данного физического расстояния (допустим 40 см) к тому или иному терму лингвистическое переменной ДИСТАНЦИЯ.

Степень принадлежности определяется функцией принадлежности

M (d), где d – расстояние до помехи.

В нашем случае расстоянию 40 см можно задать степень принадлежности к терму ОЧЕНЬ БЛИЗКО = 0,7, а к терму БЛИЗКО = 0,3. Конкретное значение степени принадлежности может проходить только при работе с экспертами.

 

 

Рисунок 1. Лингвистическая переменная и функция принадлежности.                                                       

Переменной НАПРАВЛЕНИЕ, которая может принимать значение от 0⁰ до 360⁰, зададим следующие термы: ЛЕВО, ПРЯМО, ПРАВОЕ.

Теперь необходимо задать выходные переменные. В рассматриваемом примере достаточно одной, которая будет называться РУЛЕВОЙ УГОЛ. Она может содержать термы: РЕЗКО ВЛЕВО, ВЛЕВО, ПРЯМО, ВПРАВО, РЕЗКО ВПРАВО.  Связь между входом и выходом запоминается в таблице нечетких правил.

Рисунок 2. Таблица нечетких правил.

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

Для описания неопределенности в задачах автоматического управления используется 3 подхода:

1.Вероятностный (стохастический);

2. Нечеткая логика (Fuzzy Logic);

3. Хоастические системы.

Областью внедрения алгоритмов нечеткой логики являются всевозможные экспертные системы в том числе:

1. Нелинейный подход за процессами (производство);

2. Самообучающиеся системы (классификаторы, исследование рисковых и критических ситуаций);

3. Распознавание образов;

4. Финансовый анализ (рынки ценных бумаг);

5. Исследование данных  (корпоративное хранилище);

6. Совершенствование стратегий и координация действий (например, сложное промышленное производство).

 

Недостатками нечетких систем являются:

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

2. Невозможность математического анализа нечетких систем существующими методами.

3. Применение нечеткого подхода по сравнению с вероятностным не приводит к повышению точности вычислений.

 

Инструментальные средства

Существуют различные пакеты, реализующие подходы к нечеткой логике. Наиболее яркими представителями являются следующие 3 пакета:

- FuzzyTech;

- CubiCalc;

- FuzzyCalc;

- Бизнеспрогноз.

FuzzyTech – пакет позволяет проектировать и отлаживать Fuzzy-системы. Конечным продуктом разработки системы является генерирующий при помощи программных модулей пакет содержит два редактора:

1. Редактор для создания и работы с лингвистическими переменными;

2. Редактор для работы с базой Fuzzy-правил.

Редактор для работы с лингвистическими переменными позволяет графически определить для каждого из возможных значений функцию принадлежности. В этом пакете функция принадлежности определяется при помощи координат или так называемых точек определения. Точки определения связывают линейными или нелинейными функциями. В пакете, как правило, используется четыре стандартные функции z_i, λ_i, p_i, s_i.

Функции принадлежности обычно нормализуют стандартные MBF-функции и задаются графически по следующему алгоритму:

Шаг 1.  Для каждого значения лингвистической переменной определяется самое типичное численное значение. В этой точки функции принадлежности присваивается значение единица.

Шаг 2. Значение ноль присваивается функции принадлежности в граничной точке, которая является самой типичной уже для другого (соседнего) значения лингвистической переменой.

Шаг 3. Точки 1 и 0 связываются соответствующими линиями.

Шаг 4. Для самого правого и самого левого на оси X значения лингвистической переменной используется соответствующий S-тип и Z-тип функции принадлежности.

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

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

1. MIN – MAX

2. MIN – AVG

3. GAMMA

 

Пример:

 Моделирование работы светофора в нечеткой логике.

В предлагаемом нечетком светофоре время цикла остается постоянным, однако, время его работы в режиме зеленого света должно меняться в зависимости от количества подъезжающих к перекрестку машин. Пусть время цикла традиционного и нечеткого светофоров будет одинаковым и равным 1мин.=60сек. Длительность зеленого света обычного светофора зададим 30сек., тогда красный свет будет гореть тоже 30сек.

Для работы нечеткого светофора на перекрестке улиц Север-Юг (СЮ) и Запад-Восток (ЗВ) необходимо установить 8 датчиков (рис.1), которые считают проехавшие мимо них машины.

 

Светофор использует разности показаний четырех пар датчиков: (Д1-Д2), (Д3-Д4), (Д5-Д6) и (Д7-Д8). Таким образом, если для улицы СЮ горит зеленый свет, машины проезжают перекресток и показания двух пар датчиков равны: Д1=Д2, Д5=Д6, а, следовательно, их разность равна нулю. В это же время на улице ЗВ перед светофором останавливаются машины, которые успели проехать только Д4 и Д7. В результате можно рассчитать суммарное количество автомобилей на этой улице следующим образом:

(Д4-Д3)+(Д7-Д8)=(Д4-0)+(Д7-0)=Д4+Д7.

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

Поскольку работа светофора зависит от числа машин на обеих улицах и текущего времени зеленого света, для нашей подпрограммы предлагается использовать 3 входа: число машин на улице СЮ по окончанию очередного цикла, число машин на улице ЗВ по окончанию цикла и время зеленого света нечеткого светофора.

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

• малое (10-25сек.);
• среднее(20-40сек.);

· большое(35-50сек.).

Рис.2. Функция принадлежности первой входной переменной.

Аналогично, термы для двух оставшихся переменных будут (рис.3):

• очень малое (0-18);
• малое (16-36);
• среднее (34-56);
• большое (54-76);

· очень большое (72-90).

Рис.3. Функция принадлежности второй и третьей входных переменных.

Так как суть работы светофора состоит в изменении времени зеленого света, в качестве выходного параметра предлагается использовать величину этого изменения. Термы в этом случае будут следующие:

• уменьшить (-20-0сек.);
• не изменять (-15-15сек.);
• увеличить (0-20сек.).

   
Рис.4. Функция принадлежности выходной переменной.

Кроме того, в подпрограмму записывается таблица правил на основе условных высказываний, которая формирует выходное значение исходя из величин входных параметров, например:

Если (число машин на улице СЮ=малое)&(число машин на улице ЗВ=большое)&(время зеленого света на улице СЮ=большое), то (время зеленого света=уменьшить).

 

Эволюционные вычисления

Они имеют 3 основных направления:

1 часть: Эволюционные стратегии

2 часть: Эволюционное моделирование (генетические алгоритмы)

3 часть: Эволюционное программирование

 

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

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

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

ГА используют случайный направленный поиск и могут быть использованы для получения субоптимальных решений.

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

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

2. Стохастические задачи.

3. Динамические задачи с блуждающим оптимизмом.

4. Задача комбинаторной оптимизации большой размерности.

5. Задача прогнозирования и распознавания образов.

Каждое решение задачи (особь) в ГА представлено в виде хромосомы – стринга элементов (строки, генов). Хромосома может быть представлена в двоичном, десятичном (целом или вещественном)  представлении, что делает его применимым для широкого спектра задач, для которых не применимы или не эффективны строгие математические методы.

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

ГА = (Р⁰, λ, L, S, P, f, t), где

Р⁰  = (а⁰_i …а⁰_λ) – исходная популяция (одно поколение решений, представленное хромосомами);

а⁰_i – решение задачи в виде одной хромосомы;

λ – размер популяции (целое число);

L – длина каждой хромосомы популяции (целое число);

S – оператор отбора (репродукции);

Р – отображение, определяющее оператор рекомбинации;

f – целевая функция (fitness функция);

t – критерий остановки алгоритма.

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

Выделяют следующие особенности алгоритма:

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

2. Каждая новая популяция лучше в смысле целевой функции, чем предыдущая.

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

Простой генетический алгоритм использует 3 основных оператора:

1. Репродукция (оператор отбора);

2. Кроссинговер (скрещивание);

3. Мутация (воздействие внешней среды);

Простой ГА можно представить простой схемой:

 

 

   

 

 

1. Создание исходной популяции. На интервале поиска случайно формируется исходное решение.

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

3. Создание потомков выбранных пар. Оператор кроссинговера обычно   выполняется в 3 этапа:

1-й этап. Две хромосомы А = а₁  а₂…а_n  и В = b₁ b₂…b_n выбираются из текущей популяции с помощью оператора репродукции.

2-й этап. Случайно выбирается точка кроссинговера – число k, которая находится в пределах 1≤ k ≥ n, где n – длина хромосомы.

3-й этап. Хромосомы А и В обмениваются частями после k-позиции и образуют две новые хромосомы.

A' = a₁a₂…a_k b_k+1…b_L

B' = b₁b₂…b_k   a_k+1…a_L

A = 101 10101

B = 110 01010

A' = 10101010

               B' = 11010101

4. Оператор мутации. Случайным образом с заданной вероятностью изменяется 1ген в хромосоме. Оператор мутации выполняется в 2 этапа:

        1-й этап. В хромосоме А = a₁a₂…a_L-k…a_L-1a_L  определяется случайным образом позиция гена, который будет подвержен мутации, где L – длина хромосомы (количество генов в стринге), а k – случайная величина, которая изменяется в диапазоне 0 ≤ k ≥ L.

         2-й этап. Значение гена соответственного выбранной позиции заменяют противоположным (инверсным) тем самым формируя новую хромосому А' = a₁a₂…a_L-k'…a_L-1a_L  

                A = 10 0 10111

                A' =10 1 10111.

Для усечения размера популяции работает оператор редукция. В большинстве случаев используют пропорциональный отбор на основе колеса рулетки.

Далее происходит проверка условия остановки алгоритма. Самым простым критерием остановки алгоритма исполнение достижения количества повторений алгоритма.

Пример:

На отрезке от 0 до 31 найти экстремум функции (максимум) в функции y = x².

 

 

Начальный этап работы генетического алгоритма приведен в таблице:

№ хромосомы	Начальная популяция особей	Десятичное значение k	Значение f(x)		Среднее значение (x)	Максимальное значение
1	01101	13	169	0,14	293	576
2	11000	24	576	0,49
3	01000	8	64	0,06
4	10011	19	361	0,31

 

1. Сформирована исходная популяция хромосом случайным образом в заданном интервале. Количество хромосом на заданном интервале задается пользователем.

2. Переведем в десятичную систему каждую из хромосом и подставим в fitness – функцию, получив значение f(x).

3. Произведем оценку полученных хромосом с помощью вероятности попадания хромосомы в следующую популяцию

    P(j) =

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

M = P_j * N,  где P_j  - вероятность, а N – мощность популяции.

Число копий хромосомы, переходящих в следующее поколение иногда определяется по следующей формуле:

 = , где  - среднее значение хромосом в популяции.

Расчетные значения копий хромосом:

1.) 0,56

2.) 1,97

3.) 0,22

4.) 1,23

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

                                                                                             Кроссинговер

№ хромосомы	Популяция после репродукции	Пары хромосом для кроссинговера	Популяция после кроссинговера	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
1	01101	1 - 2	01100	144	439	729
2	11000	1 - 2	11001	625
3	11000	3 - 4	11011	729
4	10011	3 - 4	10000	256

 

Одноточечный оператор кроссинговера выполняется с заданной вероятностью Р_с ≈ 0,5, т.е. отобранные хромосомы не обязательно подвергнуты кроссинговеру и образуют потомков. Хромосомы, которые должны пройти кроссинговер или не пройти, отбирают из отобранных пар.

Для хромосом 1 и 2:

А = 01101

В = 11000

1 ≤ k ≤ 4, k = 4 – точка перед пятой позицией

А' = 01100

В' = 11001

Пары хромосом для оператора кроссинговера формируют на стадии моделирования вращения колеса рулетки. При первом вращении получают первую хромосому – родителя, при втором – вторую.

                                                                                   Оператор мутации

№ хромосомы	Популяция кроссинговера	Новая популяция после мутации	Десятичное значение x	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
1	01100	01100	12	144	496,5	961
2	11001	11001	25	625
3	11011	11111	31	961
4	10000	10000	16	256

 

Мутация произведена с третьей хромосомой с третьим разрядом. Оператор мутации также выполняется с заданной вероятностью Р_м ≈ 0,0001

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

 

Создание исходной популяции

Существует основных 3 способа создания исходной популяции: