15. Генерация альтернатив решений: понятие генетического алгоритма.
Генетические алгоритмы. Идея использования генетических алгоритмов может рассматриваться как разновидность метода случайного поиска. Наименование "генетический алгоритм" происходит из аналогии представления сложной структуры посредством вектора ее компонентов, которое широко используется биологами для представления генетической структуры хромосом. В процессе анализа и решения сложной проблемы мы часто интуитивно комбинируем известные частичные решения, пытаясь найти решение общей задачи как комбинацию частных решений, предполагая при этом, что комбинация, состоящая из лучших вариантов, даст лучшее решение. Аналогия не вполне точная, но полезная для понимания идеи генетического алгоритма. Таким образом, в методе генетических алгоритмов сразу встает вопрос, какие параметры или характеристики при анализе ситуации следует варьировать, а какие сохранить без изменения. От этого, конечно, зависят и результаты анализа. Чаще всего используется два генетических оператора: crossover (перекрестный обмен) - обмен секциями хромосом родителей и mutation (мутация) - случайная модификация хромосом.
В теории генетических алгоритмов широко используется понятие схема, что значит вид или форма. Поясним это понятие следующим примером. Пусть две хромосомы, состоящие из 0 и 1, представлены векторами, показанными на рис.
1010001
1111010
1* 1* 0* *
Тогда схема для этого примера показано под чертой. В схеме символ * может быть заменен любым символом из используемого алфавита. В нашем случае нулем или единицей. Схема может рассматриваться как определение подмножеств подобных хромосом или гиперповерхностей в n-мерном пространстве. Легко представить, что каждая из хромосом может принадлежать и некоторым другим схемам. Некоторые из этих схем будут включать обе хромосомы, другие только одну. Каждый раз когда определяется годность данной хромосомы, собирается информация о возможной годности каждой схемы, которой принадлежит хромосома. Конечно, возникает вопрос сколько схем следует проанализировать. Перебор может оказаться достаточно большим. Один из путей сокращения перебора – ужесточение произвола в схемах, т.е. уменьшение в них символов * и сокращение числа самих схем. Характеристиками схем являются длина и порядок. Длина определяется числом позиций между первой и последней (т.е. не *) позициями в схеме, а порядок числом определенных (не *) позиций. Другой характеристикой является отношение годности, т.е. присутствие схемы в популяции схемы.
Операции мутации и перекрестного обмена, выбор родителей и использование схем являются инструментом влияния специалиста на ход анализа. Допуская или запрещая мутации определенных генов хромосомы и определяя точки, вокруг которых осуществляется перекрестный обмен, специалист влияет на результаты анализа ситуации и/или оценку последствий тех или иных событий.
Сегодня генетические алгоритмы нашли применение при диагностике осложнений технологических режимов нефте- и продуктопроводов, моделировании газопроводов в стационарных режимах, решении задач оптимизации инвестиционных проектов и др.
- 1. Теория принятия решений: задача принятия решений, цель, проблема, проблемная ситуация.
- 2.Измерения при формировании решений: ранжирование, парное сравнение, непосредственная оценка, виды неопределенностей и их измерение.
- 3.Виды экспертиз.
- 4.Метод Дельфы
- 5. Дерево целей и решений.
- 6.Определение усредненного мнения экспертов (среднее арифметическое, среднее геометрическое, мода, медиана Кемени
- 7.Определение согласованности мнений экспертов (коэффициент конкордации).
- 8.Виды критериев оптимальности и их содержание.
- 9. Критериальный анализ ситуации: метод базовых шкал, ранжирование и выбор критериев.
- 10.Нечеткие множества и основные операции над ними.
- 11.Экспертные методы определения функций принадлежности.
- 12. Аналитический и оптимизационный методы определения функций принадлежности.
- 13. Нечеткая задача оптимизации выбора вариантов проектов.
- 14. Модели стохастического математического программирования
- 15. Генерация альтернатив решений: понятие генетического алгоритма.
- 16. Генерация альтернатив решений: Дерево решений
- 17. Многокритериальная оптимизация. Проблемы многокритериальной оптимизации
- 18. Многокритериальная оптимизация. Множество Парето.
- 19. Многокритериальная оптимизация. Метод идеальной точки.
- 20. Принятие решений по многим критериям: Метод последовательных уступок
- 21. Принятие решений по многим критериям: Парето оптимальное решение
- 23.Принятие решений по многим критериям: Гарантированные достоинства и недостатки.
- 24.Принятие решений по многим критериям: Правило Борда.
- 25.Принятие решений по многим критериям: Принцип Беллмана-Заде
- 26. Принятие решений по многим критериям: Турнирная таблица
- 30.Согласование групповых решений: принцип большинства голосов, принцип диктатора, принцип вето, идеальной точки, консенсус.
- 31.Согласование групповых решений по Парето.
- 32. Согласование групповых решений: Метод идеальной точки
- 33. Марковская модель согласования решений.
- 34. Согласования групповых решений. (принципы Курно, Парето, Эджворта).
- 35. Теория игр: платежная матрица, чистые и смешанные стратегии, решение игры.
- 36. Решение игры в чистых стратегиях. Игры с седловой точкой.
- 37.Решение игры в смешанных стратегиях. Теорема фон Неймана.
- 38.Решение матричных игр МхN (сведение к задаче линейного программирования).
- 39.Игры с природой (теория статистических решений). Особенности платежной матрицы.
- 40.Байесовские стратегии в играх с природой (частичная неопределенность).
- 41. Критерии принятия решений в играх с природой (полная неопределенность).
- 42.Марковские процессы с дискретным временем: основные понятия и определения.
- 43.Игры с природой: оценка риска