АДАПТАЦИЯ И ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ

ВВЕДЕНИЕ

Нейронные сети были созданы в результате наблюдения за естественными процессами, происходящими в нервной системе живых существ, и попыток воспроизведения этих процессов. Термин нейрон, обозначающий основной исполнительный элемент искусственных нейронных сетей, был непосредственно заимствован из теории природных нервных систем.

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

Идею генетических алгоритмов высказал Дж. Холланд в конце шестидесятых - начале семидесятых годов XX века. Он заинтересовался свойствами процессов естественной эволюции (в том числе фактом, что эволюционируют хромосомы, а не сами живые существа). Холланд был уверен в возможности составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные процессы в поколениях таких хромосом. В них были реализованы механизмы селекции и репродукции, аналогичные применяемым при естественной эволюции. Так же, как и в природе, генетические алгоритмы осуществляли поиск «хороших» хромосом без использования какой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособленность. Механизм селекции заключается в выборе хромосом с наивысшей оценкой (т.е. наиболее приспособленных), которые репродуцируют чаще, чем особи с более низкой оценкой (хуже приспособленные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация - это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах.

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

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

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

Данный курсовой проект состоит из 4 разделов:

§ В первом разделе описывается предметная область, типы систем распознавания и алгоритмы их обучения.

§ Во втором разделе описывается цель курсового проекта, какими должны быть входные и выходные параметры, ограничения.

§ В третьем разделе идет описание используемых алгоритмов и обучение персептрона с точки зрения функции приспособленности.

§ В четвертом разделе представлена программная реализация используемых алгоритмов.

ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

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

Системы распознавания бывают следующих типов:

- системы распознавания объектов с учителем;

- системы распознавания объектов без обучения.

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

Работу системы с учителем можно разделять на две части: обучение и распознавание. В ходе обучения системы ей предъявляются отдельные объекты с указанием того, к какому классу относится данный объект. Затем происходит распознавание: предъявляется неизвестный объект и система сама должна определить его принадлежность. Это решение принимается на основании решающих правил.

Для распознавания большего числа образов, например, трех образов А, В и С, может быть применен персептрон, построенный по схеме, представленной на рис. 1.1.

Выходной сигнал каждого А-элемента поступает не на один, а на несколько (по числу различаемых образов) усилителей. После умножения на λ выходные сигналы поступают на сумматоры Σ, количество которых также равно числу различаемых образов. Вместо R-элемента установлено устройство, сравнивающее между собой выходные сигналы сумматоров. Предъявленный объект относится к тому образу, сумматор которого имеет наибольший сигнал.

Рис. 1.1 - Структурная схема персептрона с несколькими выходами

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

Обучение персептрона состоит из ряда последовательных тактов. В каждом такте персептрону предъявляется объект одного из образов. В зависимости от реакции персептрона на предъявленную ему фигуру производится по определенным правилам изменение коэффициентов λ _j. Оказывается возможным за некоторое конечное количество тактов привести персептрон в такое состояние, что он с достаточной уверенностью распознает предъявляемые ему фигуры. Возможны два типа алгоритмов обучения персептрона.

Первый из них не учитывает правильности ответов персептрона в процессе обучения, и изменение λ _j в каждом такте производится независимо от того, «узнал» или не «узнал» персептрон предъявленную в этом такте фигуру. В алгоритмах второго типа коэффициенты λ _j изменяются с учетом правильности ответов персептрона.

Алгоритм первого типа осуществляется следующим образом. Заранее уславливаются, что после обучения персептрон должен выдавать на выходе 1 при предъявлении ему, например, объектов образа А, и ноль – при предъявлении образа – В. Затем предъявляют персептрону объекты каждого из образов. В каждом такте персептрон отвечает на предъявленный ему объект возбуждением некоторых А-элементов. Обучение состоит в том, что коэффициенты λ _j возбужденных в данном такте А-элементов увеличиваются на некоторую величину (например на единицу), если в этом такте был предъявлен объект образа А, и уменьшается на эту же величину, если был предъявлен объект образа В. Естественно, что такое изменение коэффициентов λ _j должно приводить к повышению правильности ответов персептрона, так как увеличение λ _j возбужденных А-элементов приводит к увеличению сигнала на входе R-элемента, а их уменьшение – к уменьшению, если образу А будут соответствовать положительные, а образу В – отрицательные сигналы на входе R-элемента.

Второй алгоритм учитывает правильность ответов персептрона в ходе обучения. При использовании этого алгоритма коэффициенты λ _jостаются неизменными, если персептрон правильно распознал предъявленную ему в данном такте фигуру. Изменение коэффициентов λ _j производится только в тех тактах, в которых персептрон «ошибся». Изменение коэффициентов, как и в первом алгоритме, производится таким образом, чтобы повысить правильность ответов персептрона. Если, например, персептрон «ошибся» и при предъявлении объекта образа А выдал на выходе ноль вместо единицы, коэффициенты возбужденных А-элементов увеличиваются. Если был предъявлен объект образа В, а персептрон выдал на выходе R-элемента единицу, коэффициенты возбужденных А-элементов уменьшаются.

ПОСТАНОВКА ЗАДАЧИ

Целью курсового проекта является разработка приложения, позволяющего оптимизировать весовые коэффициенты персептрона с точки зрения функции приспособленности. Приложение реализовано в среде MS Visual Studio на языке C#.

Входные данные:

- 5 классов изображений разрешением 20х20 *.bmp;

- промежуток весовых коэффициентов;

- количество поколений;

- вероятность мутации;

- количество особей в 1-ой популяции;

- количество особей при отборе.

Ограничения:

При выполнении курсового проекта должны быть реализованы следующие функции:

- загрузка изображений;

- наброс весовых коэффициентов;

- преобразование коэффициентов в хромосомы;

- отбор;

- скрещивание;

- мутация.

На основании этого были построены функциональные схемы приложения, в формате IDEF приведены на рисунках 1 и 2.

Скрещивание

В данном курсовом проекте используется многоточечное скрещивание. Для каждой пары отобранных родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если генотип каждого из родителей состоит из L генов, следовательно, точка скрещивания l_k представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L - 1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков:

1. потомок, хромосома которого на позициях от 1 до l_k состоит из генов первого родителя, а на позициях от l_k + 1 до L – из генов второго родителя;

2. потомок, хромосома которого на позициях от 1 до l_k состоит из генов второго родителя, а на позициях от l_k + 1 до L – из генов первого родителя.

3. пункты 1 и 2 выполняются в цикле, меняя каждый раз точку скрещивания.

Мутация

Оператор мутации с вероятностью p_m изменяет значение гена в хромосоме на другое, генерируемое случайно из промежутка.

Вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность p_m мутации эмулируется случайным выбором числа из интервала [0, 1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению p_m.

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

Приложение разработано на языке программирования C# в среде разработки Visual Studio 2015. В этом проекте разработка происходила под OS Windows.

Описание функций и методов

Класс Genetic описывает методы генетического алгоритма (создание поколения, отбор, скрещивание, мутация);

Класс Person описывает модель точки генетического алгоритма;

Класс FitnessFunction описывает функцию приспособленности.

ЗАКЛЮЧЕНИЕ

В процессе работы над курсовым проектом были опробованы различные методы для оптимизации проектных решений, рассмотрены их отличия.

Было разработано приложение под OS Windows с помощью среды разработки Visual Studio 2015 на объектно-ориентированном языке программирования C#. Проанализировав полученные результаты, можно сделать вывод о том, что данная программа позволяет оптимизировать весовые коэффициенты персептрона.

Тестирование приложения позволило сделать следующие выводы:

1. Алгоритм обучения персептрона без учета правильности ответа дает 100% распознавание изображений.

2. Оптимизация весовых коэффициентов с помощью генетического алгоритма дает не очень хороший результат.

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

ЛИТЕРАТУРА

- Конспект лекций по дисциплине «Оптимизация проектных решений». Ковалёва И.Л., 2016 г.

- Конспект лекций по дисциплине «Методы распознавания образов». Ковалёва И.Л., 2015 г.

- Методические указания к лабораторным работам «ПЕРСЕПТРОННЫЕ НЕЙРОСЕТИ» Ковалёва И.Л., 2009 г.

- Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы, 2006 г.

Алгоритмы обработки

5 классов изображений

Оптимизация весовых коэффициентов персептрона

Параметрические ограничения

Windows приложение

Приложение 1. Схема IDEF двух уровней и UML диаграмма классов.

Оптимальное решение

Рис. 1 – Схема IDEF (первый уровень)

Рис. 2 – Схема IDEF (второй уровень)

Рис. 3 — UML диаграмма классов

Приложение 2. Исходный код класса Genetic

public class Genetic

{

private List< Person> _naturesList = new List< Person> ();

private readonly List< Person> _naturesList2Gth = new List< Person> ();

private readonly List< Person> _naturesListCrossed = new List< Person> ();

private readonly List< Person> _naturesListMutated = new List< Person> ();

private int LeftLimit;

private int RightLimit;

private int CountNatures1Gth;

private int CountNaturesForSelection;

private double CoeffMutation;

private int _numberOfGeneration = 1;

private Random _rnd = new Random();

private DataGridView _currentData;

public Genetic(string count, string Lx1, string Rx1, string naturesForSelect, string coeffMutation)

{

int.TryParse(count, out CountNatures1Gth);

int.TryParse(Lx1, out LeftLimit);

int.TryParse(Rx1, out RightLimit);

int.TryParse(naturesForSelect, out CountNaturesForSelection);

CoeffMutation = double.Parse(coeffMutation, System.Globalization.CultureInfo.InvariantCulture);

}

public void Dispose()

{

_naturesList.Clear();

_naturesList2Gth.Clear();

_naturesListCrossed.Clear();

_naturesListMutated.Clear();

_currentData.Rows.Clear();

CountNatures1Gth = 0;

Person.Count = 0;

}

public void GetChromosoma(DataGridView data, DataGridView table3, int row) {…}

public void Create1Gth(DataGridView data, Bitmap[] bmp, int[][] A) {…}

public int[][] GetRandomNumber(int minimum, int maximum, Random rnd) {…}

public void DisplayNaturesDefault() {…}

public void Selection() {…}

private void Crossing(Bitmap[] bmp, int[][] A) {…}

public void ManyPointedCrossing(Bitmap[] bmp, int[][] A) {…}

private void CrossingTwoNaturesDouble(Person rhsNature, Person lhsNature, Bitmap[] bmp, int[][] A, out Person changedNature1, out Person changedNature2) {…}

public void DoMutation(Bitmap[] bmp, int[][] A) {…}

}

Приложение 3. Исходный код класса Person

public class Person

{

public static int Count { get; set; }

public int Number { get; set; }

public int[][] Lambda { get; set; }

public string Сhromosome { get; set; }

public double ResultOfFunc { get; set; }

public double RouletteValue { get; set; }

public Person(Bitmap[] bmp, int[][] A, string chr)

{

Lambda = CreateLambda(chr);

ResultOfFunc = GetResultOfFunc(bmp, A);

Сhromosome = chr;

Number = Count;

Count++;

}

public Person(Bitmap[] bmp, int[][] A, int[][] L)

{

Lambda = L;

ResultOfFunc = GetResultOfFunc(bmp, A);

Сhromosome = CreateСhromosome(L);

Number = Count;

Count++;

}

private int[][] CreateLambda(string chr)

{

string[] temp = chr.Split(' ');

int[][] L = new int[5][];

int k = 0;

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

{

L[i] = new int[50];

for (int j = 0; j < 50; j++)

{

L[i][j] = Convert.ToInt32(temp[k]);

k++;

}

return L;

}

private string CreateСhromosome(int[][] L)

{

string chromosoma = " ";

foreach (var item in L)

{

foreach (var it in item)

{

chromosoma += it.ToString() + " ";

}

return chromosoma;

}

private double GetResultOfFunc(Bitmap[] bmp, int[][] A)

{

return FitnessFunction.GetResult(bmp, A, Lambda);

}

Приложение 4. Исходный код класса FitnessFunction

public class FitnessFunction

{

private const int LA = 50;

private static Random rnd = new Random();

public static double GetResult(Bitmap[] bmp, int[][] Ael, int[][] Lel)

{

int[] A = YesNo(bmp[rnd.Next(0, 9)], Ael, Lel);

int[] B = YesNo(bmp[rnd.Next(10, 19)], Ael, Lel);

int[] C = YesNo(bmp[rnd.Next(20, 29)], Ael, Lel);

int[] D = YesNo(bmp[rnd.Next(30, 39)], Ael, Lel);

int[] E = YesNo(bmp[rnd.Next(40, 49)], Ael, Lel);

int FA = (A[0] - A[1]) + (A[0] - A[2]) + (A[0] - A[3]) + (A[0] - A[4]);

int FB = (B[1] - B[0]) + (B[1] - B[2]) + (B[1] - B[3]) + (B[1] - B[4]);

int FC = (C[2] - C[0]) + (C[2] - C[1]) + (C[2] - C[3]) + (C[2] - C[4]);

int FD = (D[3] - D[0]) + (D[3] - D[1]) + (D[3] - D[2]) + (D[3] - D[4]);

int FE = (E[4] - E[0]) + (E[4] - E[1]) + (E[4] - E[2]) + (E[4] - E[3]);

return FA + FB + FC + FD + FE;

}

private static int[] YesNo(Bitmap bmp, int[][] A, int[][] L)

{

int p = 0;

int[] temp = new int[400];

for (byte i = 0; i < bmp.Height; i++)

{

for (byte j = 0; j < bmp.Width; j++)

{

if (bmp.GetPixel(i, j).R == 0)

{

temp[j + p] = 1;

}

else

{

temp[j + p] = 0;

}

p += 20;

}

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

{

int summ = 0;

for (int j = 0; j < 400; j++)

summ += temp[j] * A[j][i];

A[405][i] = summ;

if (summ > = 1)

A[406][i] = 1;

else A[406][i] = 0;

}

int[] summs = new int[5];

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

summs[0] += L[0][i] * A[406][i];

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

summs[1] += L[1][i] * A[406][i];

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

summs[2] += L[2][i] * A[406][i];

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

summs[3] += L[3][i] * A[406][i];

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

summs[4] += L[4][i] * A[406][i];

return summs;

}

ВВЕДЕНИЕ

Данный курсовой проект состоит из 4 разделов:

§ В первом разделе описывается предметная область, типы систем распознавания и алгоритмы их обучения.

§ В четвертом разделе представлена программная реализация используемых алгоритмов.

ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

Системы распознавания бывают следующих типов:

- системы распознавания объектов с учителем;

- системы распознавания объектов без обучения.

Рис. 1.1 - Структурная схема персептрона с несколькими выходами

ПОСТАНОВКА ЗАДАЧИ

Входные данные:

- 5 классов изображений разрешением 20х20 *.bmp;

- промежуток весовых коэффициентов;

- количество поколений;

- вероятность мутации;

- количество особей в 1-ой популяции;

- количество особей при отборе.

Ограничения:

При выполнении курсового проекта должны быть реализованы следующие функции:

- загрузка изображений;

- наброс весовых коэффициентов;

- преобразование коэффициентов в хромосомы;

- отбор;

- скрещивание;

- мутация.

На основании этого были построены функциональные схемы приложения, в формате IDEF приведены на рисунках 1 и 2.

АДАПТАЦИЯ И ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ

12 3 Следующая ⇒