А.8 Порядок контроля и приёмки

Контроль над проделанной работой осуществляется преподавателем. Так же необходимо представить отчет в печатном виде.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

 

Разработал: ст. гр. ВПР31 Кабатов Андрей Юрьевич

Тема: Решение задачи о ранце с помощью генетического алгоритма

 

Дата _________________ Подпись ______________

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

ПРИЛОЖЕНИЕ Б. UML - ДИАГРАММА КЛАССОВ

На данной UML-диаграмме представлена модель, где:

Chromosomeи Backpack - являются агрегатами класса Goldberg.

 

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

ПРИЛОЖЕНИЕ В. ОПИСАНИЕ КЛАССОВ

В ходе разработки курсового проекта были разработаны и реализованы следующие классы:

· Chromosome;

· Backpack;

· Goldberg.

Класс Chromosome –является для создания хромосом.

Класс Backpack – является классом, который служит для заполнения рюкзака.

Класс Goldberg – является классом, который служит для выполнения генетического алгоритма.

Ниже приведено описание классов, полей и методов.

Таблица Б.1 – Основные поля и методы класса Chromosome.

Название функции/поля	Параметры	Назначение
BitArray _bits	+	Биты.
Chromosome(int length)	+	Длина битового массива.
Chromosome(bool[] values)	+	Копируем битовый массив
intLength	+	Возвращает длину хромосомы
void Print()	+	Вывод на экран

 

Таблица Б.2 – Основные поля и методы класса Goldberg

Название функции/поля	Параметры	Назначение
doublechanceMutation	+	Шанс мутации
doublechanceCrossover	+	Шанс кроссовера
Goldberg()	+	Конструктор
voidInit()	+	Инициализация
voidInitBackpack()	-	Инициализация рюкзака
voidInitPopulation(intlength)	-	Инициализация популяции
bool[] Values(int length)	-	Запись значений
voidWork()	+	Реализация алгоритма
void Mark(params Chromosome[] chromosomes)	-	Занесение значений в рюкзак
int[] Selection()	-	Скрещивание
intIndexOfMaxMark(int exclude, Chromosome[] chromosomes)	-	Возвращение индекса
void Mutation(Chromosome child)	-	Мутация
void NewPopulation(Chromosome childOne, Chromosome childTwo)	-	Создание новой популяции
intResult()	-	Вывод результата
bool Protection()	-	Завершение работы алгоритма
void PrintPopulation(inti)	-	Вывод популяции на экран
void PrintBackpack()	-	Вывод рюкзака

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

ПРИЛОЖЕНИЕ Г. КОД ПРОГРАММЫ

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Program

{

// Популяция

using Population = List<Chromosome>;

// Хромосома

class Chromosome

{

BitArray _bits; // Битовыймассив

/// <param name="length">Длинабитовогомассива</param>

public Chromosome(int length)

{

_bits = new BitArray(length);

}

/// <param name="values">Копируемыйбитовыймассив</param>

public Chromosome(bool[] values)

{

_bits = new BitArray(values);

}

/// <param name="Length">Возвращаетдлинухромосомы</param>

public int Length { get { return _bits.Count; } }

/// <param name="i">Индекс (снуля)</param>

public bool this[inti]

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

{

get { return _bits[i]; }

set { _bits[i] = value; }

}

public double Mark { get; set; }

public void Print()

{

foreach (bool bit in _bits)

Console.Write(Convert.ToInt32(bit));

Console.Write(" Оценка = {0:F3}", Mark);

}

}

// Рюкзак

class Backpack

{

int[] items;

public int[] cens;

readonlyint capacity;

readonlyinttotalWeigh;

/// <paramname="capacity">Количествопредметовврюкзаке</param>

/// <param name="_items">Предметы</param>

public Backpack(int _capacity, int[] _items, int[] _cens)//заполнение

{

capacity = _capacity;

items = new int[_items.Length];

for (inti = 0; i<items.Length; i++)

{

items[i] = _items[i];

totalWeigh += items[i];

}

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

cens = (int[])_cens.Clone();

}

/// <summary>

/// Возвращаетвместимостьрюкзака

/// </summary>

public int Capacity { get { return capacity; } }

/// <summary>

/// Возвращает количество предметов в рюкзаке

/// </summary>

public int Count { get { return items.Length; } }

/// <summary>

/// Возвращает суммарный вес всех предметов, входящих в рюкзачный вектор

/// </summary>

public intTotalWeight{ get { return totalWeigh; } }

/// <param name="i">Индекс (снуля)</param>

public intthis[inti]

{

get { return items[i]; }

}

public int[] GetItems() { return (int[])items.Clone(); }

public void Print()//выводнаэкран

{

Console.Write("Рюкзак: ");

foreach (int item in items)

Console.Write("{0} ", item);

}

}

 

class Goldberg

{

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

constint ERROR = 100;

double chanceMutation;

double chanceCrossover;

Random random;

Backpack backpack;

Population population, startPopulation;

public Goldberg()//конструктор

{

random = new Random();

}

public void Init()//инициализация

{

InitBackpack();

InitPopulation(backpack.Count);

chanceCrossover = 0;

while (chanceCrossover<= 0 || chanceCrossover> 1)

chanceCrossover = InitVariable("Введитешанскроссовера: ") / 100.0;

chanceMutation = 0;

while (chanceMutation<= 0 || chanceMutation> 1)

chanceMutation = InitVariable("Введитешансмутации: ") / 100.0;

//chanceCrossover = 0.99;

//chanceMutation = 0.99;

PrintBackpack();

}

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

private void InitBackpack()

{

int capacity = 0, count = 0;

capacity = InitVariable("Введитевместимостьрюкзака: ");

count = InitVariable("Введите количество предметов: ");

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

int[] items = new int[count];

int sum = 0;

bool flag = false;

for (inti = 0; i<items.Length; i++)

{

items[i] = random.Next(capacity / count, capacity);

if (!flag)

{

sum += items[i];

if (sum > capacity)

{

items[i] -= sum - capacity;

flag = true;

}

}

else continue;

}

if (sum < capacity)

items[count - 1] = count - sum;

int power = 20, buf, one, two;

while (power--!= 0)

{

one = random.Next(0, items.Length);

two = random.Next(0, items.Length);

buf = items[one];

items[one] = items[two];

items[two] = buf;

}

 

int[] cens = new int[items.Length];

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

for (inti = 0; i<items.Length; i++)

cens[i] = random.Next(30,80);

backpack = new Backpack(capacity, items, cens);

}

private void InitPopulation(int length)//инициализацияпопуляции

{

int size = 0;

size = InitVariable("Введитеразмерпопуляции: ");

//size = 4;

startPopulation = new Population();

for (inti = 0; i< size; i++)

startPopulation.Add(new Chromosome(Values(length)));

Mark(startPopulation.ToArray<Chromosome>());

}

private bool[] Values(int length)

{

bool[] values = new bool[length];

for (inti = 0; i< length; i++)

values[i] = Convert.ToBoolean(random.Next(2));

return values;

}

private intInitVariable(string query)

{

int variable = 0;

while (variable <= 0)

{

Console.Clear();

Console.WriteLine(query);

try { variable = Convert.ToInt32(Console.ReadLine()); }

catch { }

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

}

Console.Clear();

return variable;

}

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

// Алгоритм

 

public void Work()//работаалгоритма

{

if (startPopulation == null || backpack == null) return;

population = new Population();

for (inti = 0; i<startPopulation.Count; i++)

population.Add(startPopulation[i]);

 

int sum = 0, result = 0;

int counter = 0;

int[] numOfParents;

Chromosome[] children;

PrintPopulation(counter);

while (sum!= backpack.Capacity)

{

Mark(population.ToArray<Chromosome>());

numOfParents = Selection(); // Выборродителей

children = Crossover(numOfParents[0], numOfParents[1]); // Кроссовер

if (children == null) continue; // Есликроссовернепроизошел

 

// Вывод на экран

Console.WriteLine("Родители:");

population[numOfParents[0]].Print(); Console.WriteLine(); population[numOfParents[1]].Print(); Console.WriteLine();

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

// Вывод на экран

// Вывод на экран

Console.WriteLine("Дети:");

children[0].Print(); Console.WriteLine(); children[1].Print(); Console.WriteLine();

// Выводнаэкран

Mutation(children[0]); Mutation(children[1]);

// Выводнаэкран

Console.WriteLine("Дети после мутации:");

children[0].Print(); Console.WriteLine(); children[1].Print(); Console.WriteLine();

// Выводнаэкран

NewPopulation(children[0], children[1]);

// Выводнаэкран

PrintPopulation(++counter);

// Выводнаэкран

sum = 0; result = Result();

for (inti = 0; i<backpack.Count; i++)

if (population[result][i])

sum += backpack[i];

 

if (counter % ERROR == 0 &&Protection()) break;

}

 

Console.WriteLine();

Console.WriteLine("Результат:");

population[result].Print();

Console.WriteLine();

Console.WriteLine("Предметы помещенные в рюкзак: ");

for (inti = 0; i<backpack.Count; i++)

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

{

if (population[result][i]) {

Console.WriteLine("Вес: {0}, Цена: {1}", backpack[i], backpack.cens[i]);

}

}

Console.WriteLine();

Console.WriteLine("Сумма: {0}", sum); }

private void Mark(params Chromosome[] chromosomes)

{

int weight;

int capacity = backpack.Capacity;

inttotalWeight = backpack.TotalWeight;

int L = Math.Max(capacity, totalWeight - capacity);

 

foreach (Chromosome chromosome in chromosomes)

{

weight = 0;

for (inti = 0; i<chromosome.Length; i++)

if (chromosome[i]) weight += backpack[i];

if (weight <= capacity)

chromosome.Mark = 1 - Math.Sqrt(Math.Abs(weight - capacity) / Convert.ToDouble(capacity));

else

chromosome.Mark = 1 - Math.Sqrt(Math.Abs(weight - capacity) / Convert.ToDouble(L));

}

}

private int[] Selection()

{

int one = IndexOfMaxMark(-1, population.ToArray<Chromosome>());

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

int two = IndexOfMaxMark(one, population.ToArray<Chromosome>());

return new int[] { one, two };

}

private intIndexOfMaxMark(int exclude, Chromosome[] chromosomes)

{

int index = 0;

double max = 0;

for (inti = 0; i<chromosomes.Length; i++)

{

if (chromosomes[i].Mark> max &&i!= exclude)

{

max = chromosomes[i].Mark;

index = i;

}

}

return index;

}

private Chromosome[] Crossover(int one, int two)//кроссовер

{

double chance = random.NextDouble();

if (chance >= chanceCrossover) return null;

Chromosome parentOne = population[one];

Chromosome parentTwo = population[two];

Chromosome childOne = new Chromosome(backpack.Count);

ChromosoechildTwo = new Chromosome(backpack.Count);

int s = random.Next(0, parentOne.Length);

for (inti = 0; i<= s; i++)

{

childOne[i] = parentOne[i];

childTwo[i] = parentTwo[i];

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

}

for (inti = s + 1; i<parentOne.Length; i++)

{

childOne[i] = parentTwo[i];

childTwo[i] = parentOne[i];

}

Mark(childOne, childTwo);

return new Chromosome[] { childOne, childTwo };

}

private void Mutation(Chromosome child)//мутация

{

double chance = random.NextDouble();

if (chance >= chanceMutation) return;

intpos = random.Next(0, child.Length);

child[pos] =!child[pos];

Mark(child);

}

private void NewPopulation(Chromosome childOne, Chromosome childTwo)//новаяпопуляция

{

intpos = random.Next(0, population.Count);

Chromosome[] chromosomes = new Chromosome[] { population[pos], childOne, childTwo };

int best = IndexOfMaxMark(-1, chromosomes);

if (best!= 0)

{

// Выводнаэкран

Console.WriteLine("Хромосома: ");

chromosomes[best].Print();

Console.WriteLine();

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Console.WriteLine("Заменилахромосому: ");

population[pos].Print();

Console.WriteLine();

// Выводнаэкран

population[pos] = chromosomes[best];

}

Console.WriteLine();

}

private intResult()

{

int sum, max = 0, index = 0;

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

{

sum = 0;

for (int j = 0; j < population[i].Length; j++)

if (population[i][j])

sum += backpack[j];

if (sum <= backpack.Capacity&& sum > max)

{

max = sum;

index = i;

}

}

return index;

}

private bool Protection()

{

bool result = false;

ConsoleKey key = ConsoleKey.NoName;

while (key!= ConsoleKey.Y&& key!= ConsoleKey.N)

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

{

Console.WriteLine("Завершитьработуалгоритма?");

Console.WriteLine("Y - Да. N - Нет");

key = Console.ReadKey().Key;

if (key == ConsoleKey.Y) result = true;

else result = false;

}

return result;

}

// Алгоритм

// Выводнаэкран

private void PrintPopulation(inti)

{

Console.WriteLine("Популяция№{0}:", i.ToString());

foreach (Chromosome chromosome in population)

{

chromosome.Print();

Console.WriteLine();

}

}

private void PrintBackpack()

{

backpack.Print();

Console.WriteLine();

Console.WriteLine("Суммарныйвесрюкзачноговектора: {0}", backpack.TotalWeight);

Console.WriteLine("Вместимостьрюкзака: {0}", backpack.Capacity);

Console.WriteLine();

}

 

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

// Выводнаэкран

}

class Program

{

static void Main(string[] args)

{

Goldberg Goldberg = new Goldberg();

string[] menu = new string[] { "Инициализация", "Алгоритм" };

ConsoleKey key;

while (true)

{

Console.Clear();

for (inti = 0; i<menu.Length; i++)

Console.WriteLine("{0} - {1}", i + 1, menu[i]);

Console.WriteLine("0 - Выход");

key = Console.ReadKey().Key;

Console.Clear();

switch (key)

{

case ConsoleKey.D1:

Goldberg.Init();

break;

case ConsoleKey.D2:

Goldberg.Work();

break;

case ConsoleKey.D0:

return;

}

Console.WriteLine("Дляпродолжениянажмителюбуюклавишу...");

Console.ReadKey(); } } }}