Главная страница
Навигация по странице:

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

  • Преимущества данного метода

  • Основные понятия Вектор – упорядоченный набор чисел.

  • Гены – элементы кодирования наследственной информации (параметров целевой функции). В качестве генов чаще всего выступает битовое кодирование информации.

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

  • Мутация – случайное изменение генов. Случайным образом выбранный ген с некоторой вероятностью меняется на другой.

  • Пригодность (приспособленность) – значение целевой функции для данного набора параметров по отношению к требуемому значению. Принцип действия

  • Пример использования Возьмем для примера такую задачу, в которой матрица расстояний задана следующим образом

  • III. 1-4-3-2-1 Fiii=13+5+5+2=25 2) I. 1-4-3-2-1 Fi=13+5+5+2=25 2) I. 1-4-3-2-1 Fi=13+5+5+2=25 II. 1-2-3-4-1 Fii=4+9+5+5=23

  • Ответ

  • Спасибо за внимание!

  • Генетические алгоритмы. Генетические алгоритмы Подготовила студентка 18ивт3


    Скачать 1,57 Mb.
    НазваниеГенетические алгоритмы Подготовила студентка 18ивт3
    Дата05.06.2019
    Размер1,57 Mb.
    Формат файлаpptx
    Имя файлаГенетические алгоритмы.pptx
    ТипДокументы
    #56842

    Подборка по базе: Генетические алгоритмы.pptx.
    Генетические алгоритмы
    Подготовила студентка 18ИВТ3
    Козменкова Е.П.
    Что такое генетический алгоритм?

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

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

    Области применения

    Оптимизация функций
    Оптимизация запросов в базах данных
    Разнообразные задачи на графах
    Задачи компоновки
    Игровые стратегии
    Теория приближений
    Искусственная жизнь
    Био-информатика
    Синтез конечных автоматов
    Коллективный разум
    Задачи размещения
    Настройка искусственной нейронной сети
    Обучение машин

    Преимущества данного метода

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

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

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

    Пример использования
    Возьмем для примера такую задачу, в которой матрица расстояний задана следующим образом:
    1) Создадим начальную популяцию из 3 особей случайным образом и оценим их функцию приспособленности:
    I. 1-3-2-4-1 Fi=10+5+7+5=27
    II. 1-2-3-4-1 Fii=4+9+5+5=23
    III. 1-4-3-2-1 Fiii=13+5+5+2=25
    2) I. 1-4-3-2-1 Fi=13+5+5+2=25
    2) I. 1-4-3-2-1 Fi=13+5+5+2=25
    II. 1-2-3-4-1 Fii=4+9+5+5=23
    III. 1-4-3-2-1 Fiii=13+5+5+2=25
    3) Проводить повторную мутацию особи II смысла нет (если поменять местами 2 и 3 элементы, получится 1-3-2-4-1 и F=10+5+7+5=27, что больше остальных значений). Поэтому происходит мутация I особи по 2 и 3 элементам. Получаем 1-3-4-2-1. F = 10+5+8+2=25, что не приближает нас к «оптимальности» решения, из чего следует вывод, что оптимальной особью была II. Ответ: путь 1-2-3-4-1 , его длина – 23.
    Решение задачи коммивояжера на примере туристических центров Нижегородской области

    Оптимальным решением будет путь 1-6-3-2-5-4-1 и его длина – 639 км. Однако, даже проведя миллиарды итераций, мы не можем быть уверены, что это решение лучшее.
    Вывод
    Таким образом, нам удалось разобраться с базовой структурой генетических алгоритмов и применить их для решения транспортной задачи. Генетический алгоритм подходит для быстрых вычислений, однако нельзя быть точно уверенным, что конечный результат окажется самым оптимальным. Преимущества и недостатки ГА представлены ниже. Преимущества:

    Очень быстр.
    Требует минимум памяти.
    Способен дать ответ при огромных массивах входных данных за приемлемое время.
    Итерации максимально просты и понятны.
    Нет ветвлений, процесс идёт линейно.
    Подходит для больших вычислений.
    Недостатки:
    Не точен.
    Проверка ответа возможность лишь до определённой степени вероятности.
    Проверка ответа довольно продолжительна.
    Не подходит для точных вычислений.
    Распараллеливание может не дать какого-либо прироста скорости.

    Спасибо за внимание!


    написать администратору сайта