Оператор мутации.
Случайное перемешивание.
|1|6|3|5|2|4|1|
1)Случайным образом определяются границы интервала мутаций.
2)На выбранном участке выполняется перемешивание генов.
|1|6|4|5|2|3|1|
Применение метода случайного перемешивания порождает только допустимые варианты решения.
Оператор скрещивания
Метод двоичной маски
1) |1|6|3|5|4|2|1| Случайным образом определяются границы интервала обмена генным материалом.
2) |1|5|2|4|6|3|1| Генерируется случайная двоичная маска, длина которой соответствует размерам интервала обмена.
3) |1|6|4|5|3|2|1| В дочернюю хромосому помещаются гены первого родителя, соответствующей единичным битам маски. Недостающие гены выбираются из хромосомы первого родителя в порядке, в котором они присутствуют в хромосоме второго родителя.
Параметры применения операторов.
Количество мутаций на > 40% пок-и.
Ограничение поколений.
06.10.2012 Эффективные алгоритмы оптимизации на графах.
Алгоритм Дейкстры поиска кратчайшего пути между парой заданных вершин графов.
Матрица весов ребер графа С.
C(ij) - матрица весов рёбер графа
с(ij) - вес ребра между i и j
Вершин - N
Для любой вершины j определена функция d(j) - минимального расстояния от исходной точки маршрута.
Вершина может иметь статус "окрашено" или "пройдено".
В ходе построения кратчайшего пути любая вершина окрашивается однократно.
Вершина откуда s (source)
Вершина куда t (target)
Инициализация:
1.Пометить вершину S
2.Для всех вершин, кроме S определить функцию d равную бесконечности
3.Для вершины S функцию d определить равной нулю.
Итерации: пока не помечена вершина d и есть вершины способные получить метку выполнять
//неудача s и t лежат в разных подграфах
4.1. для всех непомеченных вершин выполнить пересчёт функции d(j) последующему правилу d(j) = min(d(j), (d(i)+c(ij)), где i - вершина которая получила метку последней.
4.2. Найти непомеченную вершину j для которой значение d(j)
4.3. Если min(d(j)) равно бесконечности, то неудача, иначе пометить вершину d соответствующую минимальному значению функции и указать для неё вершину из которой она получила метку.
5.Если удача, то восстановить кратчайший путь с использованием обратной ссылки (метки)
Замечание 1: Алгоритм Дейкстры строит дерево окрашенных вершин, корнем которого является вершина S.
Замечание 2: Этот алгоритм можно применить для поиска кратчайшего пути из S до всех вершин графа. Для этого достаточно поменять формулировку предусловия. Кратчайшее расстояние между вершинами S и j это значение функции d(j) на момент окрашивания вершины j.
Замечание 3: Кратчайший путь восстанавливается при помощи кратчайших ссылок.
Алгоритмы построения остова графа.
Остов - это дерево, покрывающее все вершины графа.
1)Задача построения остова имеет много допустимых решений.
2)Количество рёбер остова на единицу меньше количества вершин
3)Ребра, которые не вошли в остов называются хордами. Если рёбер в графе M, а вершин N, то хорд M - (N-1)
4)Количество хорд равно количество независимых контуров
Практическое применение
Автоматическое построение контурных уравнений в электрических цепях с применением остова.
Построение остова с применением стратегии исчерпывающего поиска в глубину
Псевдокод построения поиска в глубину с использованием рекурсии.
V - текущая вершина
U - вершина смежная V
M - множество помеченных вершин M = пустое
1)Процедура "остов" с параметром V.
1.1. Включить V во множество M.
1.2. Для всех U смежных V и не принадлежащих M выполнять
1.2.1. Добавить ребро VU в остов
1.2.2. Вызвать процедуру остов с параметром U
Построение остова методом исчерпывающего поиска в ширину
Псевдокод:
1.Пометить произвольную вершину и поставить её в очередь
2.Пока очередь не пуста, выполнять
2.1. Взять вершину из очереди.
2.2. Для всех вершин смежных к текущей
2.2.1 окрасить смежную вершину
2.2.2 добавить ребро между текущей и смежной вершиной в остов. Поставить смежную вершину в очередь.
Анализ выч. Эффективности.
N-1
N-1 0 (N2)
Применение стратегии исчерпывающего перебор оправдано тем, что она используется для построения первого варианта решения.