Лекции Определить место генетических алгоритмов в Data Mining




НазваниеЛекции Определить место генетических алгоритмов в Data Mining
Дата конвертации31.01.2013
Размер445 b.
ТипЛекции


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

  • Ращупкин Владимир


Цель лекции

  • Определить место генетических алгоритмов в Data Mining

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

  • Рассмотреть пример



Определение

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



Терминология

  • Популяция - это конечное множество особей.

  • Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов.

  • Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

  • Генотип или структура - это набор хромосом данной особи.

  • Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи {решение, точка пространства поиска).



Этапы Data Mining



Методы Data Mining

  • Базовые методы;

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

  • Генетические алгоритмы;

  • Нейронные сети.



Генетический алгоритм



Генетический алгоритм



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

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



Инициализация

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



Инициализация (пример)



Оценивание приспособленности



Оценивание приспособленности (пример)



Селекция хромосом



Селекция хромосом (пример)



Применение генетических операторов

  • Оператор скрещивания

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



Оператор скрещивания

  • Хромосомы из родительской популяции объединяются в пары случайным образом

  • В каждой хромосоме определяется точка скрещивания



Оператор скрещивания (пример)



Формирование новой популяции

  • Все предки замещаются потомками

  • Из предков и потомков выбираются худшие и отбрасываются

  • И т.д.



Формирование новой популяции (пример)



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

  • Достижение заданного оптимального значения функции приспособленности;

  • Выполнение алгоритма не приводит к улучшению уже достигнутого значения;

  • Истечение заданного количества времени (заданного количества итераций);

  • И т.д.



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



Задача коммивояжера

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



Задача коммивояжера



Задача коммивояжера



Похожие:

Лекции Определить место генетических алгоритмов в Data Mining iconЗадача нестационарной дискретной оптимизации
Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов
Лекции Определить место генетических алгоритмов в Data Mining iconЛекции цоров для уроков Алгоритмы и исполнители Содержание Алгоритмы и исполнители Основные понятия Свойства алгоритмов Способы записи алгоритмов

Лекции Определить место генетических алгоритмов в Data Mining icon"Совершенно невозможно определить место науки в нашей культуре, минуя ее историю". С. П. Капица
Совершенно невозможно определить место науки в нашей культуре, минуя ее историю
Лекции Определить место генетических алгоритмов в Data Mining iconПоиск шаблонов последовательных событий (Sequential Pattern Mining или spm) Поиск шаблонов последовательных событий (Sequential Pattern Mining или spm)
Отсутствие инструментального средства, позволяющего решать задачу spm для различных форматов входных данных
Лекции Определить место генетических алгоритмов в Data Mining iconТема «Общая характеристика грибов» Цель: определить место грибов в системе органического мира

Лекции Определить место генетических алгоритмов в Data Mining iconЛекции «Основы эхокардиографии»
Как на основании данных эхокг определить степень тяжести стеноза левого атриовентрикулярного отверстия, стеноза устья аорты
Лекции Определить место генетических алгоритмов в Data Mining iconOceanographic data (water temperature, salinity, density; currents, depths etc.) Oceanographic data (water temperature, salinity, density; currents, depths etc.)

Лекции Определить место генетических алгоритмов в Data Mining iconComplex of state standards inter-regional, interbranch and branch data exchange

Лекции Определить место генетических алгоритмов в Data Mining iconУчитель географии моу-средняя общеобразовательная
Задание. Определить крайние точки материка Ю. Америка, определить географические координаты
Лекции Определить место генетических алгоритмов в Data Mining iconСоставить классификацию алгоритмов в окружающем информационном пространстве для развития логического и алгоритмического мышления С
...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница