Файл: Лекция д т. н., профессора Курейчика В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы.doc

Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A_i теории ГА интерпретируются истинными суждениями A_i^* теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A_i в ГА, интерпретируется в ПГА некоторым утверждением A^*, выводимым в ПГА из интерпретаций A_i^* аксиом A_i и, следовательно, истинным.

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

1. 
   Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.
   
   1. 
      Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.
      
   2. 
      Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:
      

• 
  построение моделей эволюций;
  
• 
  конструирования популяций;
  
• 
  построения ЦФ;
  
• 
  разработки генетических операторов;
  
• 
  репродукции популяций;
  
• 
  рекомбинации популяций;
  
• 
  редукции;
  
• 
  адаптации.
  

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

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

---

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

3. 
   Правила вывода ГА. Фиксируется конечная совокупность предикатов П₁, П₂,…, П_k на множестве всех формул системы. Пусть П (x₁,…,x_ni+1) – какой-либо из этих предикатов (n_i0) если, для данных формул F₁,…, F_ni+1 утверждение П (F₁,…,F_ni+1 ) истинно, то говорят, что формула F_ni+1 непосредственно следует из формул F₁,…, F_ni+1 по правилу П_i .
   

Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П_i системы.

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

Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска:

• 
  «поиск – эволюция»;
  
• 
  «эволюция – поиск»;
  
• 
  «поиск – эволюция - поиск»;
  
• 
  «эволюция – поиск - эволюция».
  

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

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

---

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

---

Выводы

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

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

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

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

Контрольные вопросы

1. 
   Поясните смысл понятия "генетические алгоритмы".
   
2. 
   В чем заключается эволюционный поиск?
   
3. 
   Приведите основные цели и задачи генетических алгоритмов.
   
4. 
   Выделите основные отличительные особенности ГА.
   
5. 
   Приведите основные понятия и определения генетических алгоритмов.
   
6. 
   Что такое целевая функция в генетических алгоритмах?
   
7. 
   Перечислите предварительные этапы работы генетических алгоритмов.
   
8. 
   Каким образом в генетических алгоритмах осуществляется выбор способа представления решения?
   
9. 
   Как производится разработка операторов случайных изменений в ГА?
   
10. 
    Какие способы «выживания» решений в ГА вы знаете?
    
11. 
    Поясните, как создается начальная популяция альтернативных решений?
    
12. 
    Приведите различные модели размножения, используемые в генетических алгоритмах.
    
13. 
    Дайте определение понятия принципа и приведите примеры принципов построения генетических алгоритмов.
    
14. 
    Каким образом определяется эффективность генетического алгоритма?
    
15. 
    Приведите четыре основных принципа формирования начальной популяции.
    
16. 
    Дайте определение оператора в алгоритме и генетического оператора.
    
17. 
    Поясните оператор репродукции.
    
18. 
    Приведите основные виды операторов репродукции (селекции).
    
19. 
    Приведите основные стратегии реализации оператора репродукции.
    
20. 
    Определите понятие «предварительная сходимость алгоритма».
    
21. 
    Дайте определение оператора кроссинговера.
    
22. 
    Поясните реализацию простого оператора кроссинговера.
    
23. 
    Поясните реализацию двух точечного оператора кроссинговера.
    
24. 
    В чем заключается реализация упорядоченного оператора кроссинговера.
    
25. 
    Поясните реализацию частично-соответствующего оператора кроссинговера.
    
26. 
    В чем заключается реализация циклического оператора кроссинговера.
    
27. 
    Приведите пример работы универсального оператора кроссинговера.
    
28. 
    Поясните основную идею жадного алгоритма.
    
29. 
    В чем заключается реализация жадного оператора кроссинговера.
    
30. 
    Приведите пример работы жадного оператора кроссинговера.
    
31. 
    Опишите основные операторы мутации.
    
32. 
    Поясните реализацию простого оператора мутации.
    
33. 
    В чем заключается реализация оператора инверсии.
    
34. 
    Поясните реализацию оператора транслокации.
    
35. 
    В чем заключается реализация оператора транспозиции.
    
36. 
    Приведите пример работы оператора сегрегации.
    
37. 
    Поясните реализацию оператора удаления.
    
38. 
    В чем заключается реализация оператора вставки.
    
39. 
    Поясните принципы работы оператора редукции.
    
40. 
    В чем заключается оператор рекомбинации.
    
41. 
    Приведите примеры операций объединения, пересечения и разности хромосом и популяций.
    
42. 
    Приведите пример кортежа и декартово произведение популяций.
    
43. 
    Определите понятия «отношение» и «отношение популяций».
    
44. 
    Приведите основные свойства отношений.
    
45. 
    Поясните понятие нечеткое (расплывчатое) множество.
    
46. 
    Поясните основные логические операции над популяциями.
    
47. 
    Охарактеризуйте простой ГА.
    
48. 
    Поясните смысл понятия "шаблон" в ПГА.
    
49. 
    Приведите фундаментальную теорему для ПГА.
    
50. 
    Приведите часть фундаментальной теоремы ПГА для ОР.
    
51. 
    Приведите часть фундаментальной теоремы ПГА для ОК.
    
52. 
    Приведите часть фундаментальной теоремы ПГА для ОМ.
    
53. 
    Приведите пример вычисления выживающих шаблонов на основе фундаментальной теоремы ПГА.
    
54. 
    Приведите пример построения произвольной формальной системы генетических алгоритмов.
    
55. 
    Поясните основные стратегии взаимодействия методов эволюционного и локального поиска.
    

---

---