докладик (1002208)

Файл №1002208 докладик (Доклад - Генетические алгоритмы, распознавание изображений)докладик (1002208)2016-04-06СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Генетические алгоритмы, распознавание изображений

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

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

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

Хромосома – это возможное решение нашей задачи, не важно какое, правильное или нет.

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

Популяция – набор хромосом текущей эпохи.

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

Кроссовер отвечает за передачу признаков родителей своим потомкам, в самой простой реализации он создаёт новую хромосому из генов двух родителей, «донор» очередного гена выбирается произвольным образом.

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

Fitness-функция: Как и в жизни – не приспособленные виды должны погибать, «чистить» нашу популяцию будет последняя функция, называемая функцией приспособления, или Fitness-функцией. Для каждой хромосомы эта функция возвращает число, обратно пропорциональное «приспособленности» этой хромосомы, на нее накладываются условия: Значение Fitness от идеального решения = 0

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

Теперь можно сформулировать вариант алгоритма

1. Обозначить номер эпохи = 0, создать популяцию хромосом, в генах которых будет произвольная, не противоречащая задаче, информация

2. Посчитать приспособленность популяции

3. Выбрать из популяции особь А

4. С вероятностью P(скрещивания) выбрать особь B и применить оператор кроссовера, результирующую особь занести в новую популяцию.

5. С вероятностью P(мутации) выполнить мутацию произвольной особи, результирующую особь занести в новую популяцию

6. Выполнить операции 3,4,5 n раз, где n >= размера популяции

7. Создать новую популяцию из лучших особей существующей и только что сформированной популяции

8. Увеличить номер текущей эпохи

9. Если результат работы удовлетворителен – остановка алгоритма, иначе – переход к шагу 2.

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

public class Chromosome : IComparable

{

public double[] gens;

static Random random = new Random();

public Chromosome()

{

this.gens = new double[3];

for (int i = 0; i < 3; i++)

{

this.gens[i] = random.NextDouble() * 100;

}

this.fit = fitness(this);

}

public int CompareTo(object obj)

}

Значение 100 выбрано для примера, это не ограничит общности, даже если искомая парабола будет иметь кофээфициенты >100. Отметим метод CompareTo, позволяющий нам сортировать списки объектов Chromosome.

public class Population

{

Random random = new Random();

public List<Chromosome> population;

public int count;

public double crossProbability;

public double MutationProbability;

public int age;

public Population()

{

for (int i = 0; i < 5000; i++)

{

this.population.Add(new Chromosome());

}

}

public void GoToNextGeneration()

{

Chromosome chromosome;

for (int i = 0; i < count; i++)

{

chromosome = population[i];

if (random.NextDouble() < crossProbability)

{

population.Add(Cross(chromosome,population[random.Next(count)]));

}

}

for (int i = 0; i < population.Count; i++)

{

if (random.NextDouble() < MutationProbability)

{

population.Add(Mutate(population[i]));

}

}

population.Sort();

population.RemoveRange(count,population.Count-count);

age++;

}

Chromosome Cross(Chromosome a, Chromosome b)

Chromosome Mutate(Chromosome a)

double Fitness(Chromosome a)

}



Вот она, эволюция в двадцати строчках! Это и будет сердцем нашей программы. В первой части мы получаем потомство от уже существующей популяции, и добавляем его в конец списка, т.е. все «дети» будут находится под номерами большими чем count.

Второй шаг – мутация, было бы логично мутировать саму хромосому, а не добавлять мутировавший клон, но в этом случае мы теряем содержащееся в исходной хромосоме решение, а оно может быть лучшим в популяции. Наконец, в конце мы сортируем всю нашу получившуюся популяцию по возрастанию Fitness функции, (следовательно – по убыванию правильности решения) удаляем наименее «приспособленные» хромосомы, и увеличиваем номер текущей эпохи.

Давайте рассмотрим, что же представляют собой три последние функции, производящий операции над нашими хромосомами?

Chromosome Cross(Chromosome a, Chromosome b)

{

double[] pair = new double[3];

for (int i = 0; i < 3; i++)

{

if ((random.Next() % 2) == 0)

{

pair[i] = a.Gens[i] + (b.Gens[i] - a.Gens[i]) * 0.1;

}

else

{

pair[i] = b.Gens[i] - (b.Gens[i] - a.Gens[i]) * 0.1;

}

}

Chromosome result = new Chromosome(pair);

return result;

}

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

Поправка (b.Gens[i] — a.Gens[i]) * 0.1 сделана чтобы как-то разнообразить популяцию новыми генотипом.

Chromosome Mutate(Chromosome a)

{

double[] pair = (double[])a.Gens.Clone();

int geneNum = random.Next(3);

pair[geneNum] = random.NextDouble() * 100;

return new Chromosome(pair, a.chromosomeSettings);

}

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

double GetFitness(Chromosome a)

{

double result = 0;

double temp;

for (int i = 0; i < funcLength; i++)

{

temp = Math.Abs(Func(i, a.Gens) - funcArray[i]);

result += temp;

}

return result;

}

double Func(double x, double[] gens)

{

double result = 0;

for (int i =2; i >= 0; i--)

{

result += gens[2-i] * Math.Pow(x, i);

}

return result;

}

Массив funcArray получается сканированием картинки снизу вверх по столбцам, каждый столбец – индекс массива, высота первой найденной черной точки в столбце – значение.
Функция Func – возвращает значение уравнения 2й степени в точке x, с коэффициентами из массива gens
Получается Fitness – это сумма «погрешностей», для каждой точки нашей параболы, которая есть на рисунке. Такая функция не имеет единственный минимум, но, тем не менее, обеспечивает достаточную сходимость алгоритма.



Результат:



При количестве хромосом в популяции = 5000, на 25ом поколении мы получаем достаточно близкое сходство.

Данный алгоритм можно расширить на кривые любого порядка

Характеристики

Тип файла
Документ
Размер
59 Kb
Тип материала
Высшее учебное заведение

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата

Доклад - Генетические алгоритмы, распознавание изображений
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6376
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее