Результат выполнения лабораторной работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение
высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

КАФЕДРА 43

ОЦЕНКА

ПРЕПОДАВАТЕЛЬ

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

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №3

Решение задачи коммивояжера с помощью генетических алгоритмов

по дисциплине: ЭВОЛЮЦИОННАЯ МЕТОДОЛОГИЯ В ПРОГРАММНОЙ ИНЖЕНЕРИИ

РАБОТУ ВЫПОЛНИЛ(А)

СТУДЕНТ(КА) ГР.	Z7430m		А.С. Хромцова
	номер группы	подпись, дата	инициалы, фамилия
Студенческий билет №	2017/2649

Санкт-Петербург 2019

Общие сведения

Задача коммивояжера (ЗК) считается классической задачей генетиче-

ских алгоритмов. Она заключается в следующем: путешественник (или

коммивояжер) должен посетить каждый из базового набора городов и вер-

нуться к исходной точке. Имеется стоимость билетов из одного города в

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

ных средств была минимальной. Поисковое пространство для ЗК- множе-

ство из N городов. Любая комбинация из N городов, где города не повто-

ряются, является решением. Оптимальное решение – такая комбинация,

стоимость которой (сумма из стоимостей переезда между каждыми из го-

родов в комбинации) является минимальной.

ЗК – достаточно стара, она была сформулирована еще в 1759 году

(под другим именем). Термин «Задача коммивояжера» был использован в

1932г. в немецкой книге «The traveling salesman, how and what he should to

get commissions and be successful in his business», написанную старым ком-

мивояжером.

Задача коммивояжера была отнесена к NP-сложным задачам. Суще-

ствуют строгие ограничения на последовательность, и количество городов

может быть очень большим (существуют тесты, включающие несколько

тысяч городов).

Кажется естественным, что представление тура – последовательность

(i1, i2, … , in), где (i1, i2, … , in) – числа из множества (1 … n), представляю-

щие определенный город. Двоичное представление городов неэффективно,

т.к. требует специального ремонтирующего алгоритма: изменение одиноч-

ного бита может повлечь неправильность тура.

В настоящее время существует три основных представления пути: со-

седское, порядковое и путевое. Каждое из этих представлений имеет соб-

ственные полностью различные операторы рекомбинации.

Цель работы

Решение задачи коммивояжера с помощью генетического алгоритма.

Задание на лабораторную работу

Реализовать с использованием генетических алгоритмов решение задачи коммивояжера по индивидуальному заданию согласно номеру варианта.

Сравнить найденное решение с представленным в условии задачи оптимальным решением.

Представить графически найденное решение.

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

ХМL с координатами 49 городов

<?xml version="1.0" encoding="UTF-8"?>

-<CityList>

</CityList>

Результат выполнения лабораторной работы

Cities.cs

using System;

using System.Collections;

using System.Collections.Generic;

using System.Text;

using System.Data;

using System.IO;

using System.Globalization;

namespace Tsp

{

/// <summary>

/// This class contains the list of cities for this test.

/// Each city has a location and the distance information to every other city.

/// </summary>

public class Cities : List<City>

{

/// <summary>

/// Determine the distances between each city.

/// </summary>

/// <param name="numberOfCloseCities">When creating the initial population of tours, this is a greater chance

/// that a nearby city will be chosen for a link. This is the number of nearby cities that will be considered close.</param>

public void CalculateCityDistances( int numberOfCloseCities )

{

foreach (City city in this)

{

city.Distances.Clear();

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

{

city.Distances.Add(Math.Sqrt(Math.Pow((double)(city.Location.X - this[i].Location.X), 2D) +

Math.Pow((double)(city.Location.Y - this[i].Location.Y), 2D)));

}

foreach (City city in this)

{

city.FindClosestCities(numberOfCloseCities);

}

/// <summary>

/// Open the XML file that contains the list of cities.

/// </summary>

/// <param name="fileName">Name of the XML file.</param>

/// <returns>The city list.</returns>

/// <exception cref="FileNotFoundException">fileName parameter is invalid.</exception>

/// <exception cref="InvalidCastException">XML File is not properly formatted.</exception>

public void OpenCityList(string fileName)

{

DataSet cityDS = new DataSet();

try

{

this.Clear();

cityDS.ReadXml(fileName);

DataRowCollection cities = cityDS.Tables[0].Rows;

foreach (DataRow city in cities)

{

this.Add(new City(Convert.ToInt32(city["X"], CultureInfo.CurrentCulture), Convert.ToInt32(city["Y"], CultureInfo.CurrentCulture)));

}

finally

{

cityDS.Dispose();

}

Population.cs

using System;

using System.Collections;

using System.Collections.Generic;

using System.Text;

namespace Tsp

{

class Population : List<Tour>

{

/// <summary>

/// Private copy of the best tour found so far by the Genetic Algorithm.

/// </summary>

private Tour bestTour = null;

/// <summary>

/// The best tour found so far by the Genetic Algorithm.

/// </summary>

public Tour BestTour

{

set

{

bestTour = value;

}

get

{

return bestTour;

}

/// <summary>

/// Create the initial set of random tours.

/// </summary>

/// <param name="populationSize">Number of tours to create.</param>

/// <param name="cityList">The list of cities in this tour.</param>

/// <param name="rand">Random number generator. We pass around the same random number generator, so that results between runs are consistent.</param>

/// <param name="chanceToUseCloseCity">The odds (out of 100) that a city that is known to be close will be used in any given link.</param>

public void CreateRandomPopulation(int populationSize, Cities cityList, Random rand, int chanceToUseCloseCity)

{

int firstCity, lastCity, nextCity;

for (int tourCount = 0; tourCount < populationSize; tourCount++)

{

Tour tour = new Tour(cityList.Count);

// Create a starting point for this tour

firstCity = rand.Next(cityList.Count);

lastCity = firstCity;

for (int city = 0; city < cityList.Count - 1; city++)

{

// Keep picking random cities for the next city, until we find one we haven't been to.

if ((rand.Next(100) < chanceToUseCloseCity) && ( cityList[city].CloseCities.Count > 0 ))

{

// 75% chance will will pick a city that is close to this one

nextCity = cityList[city].CloseCities[rand.Next(cityList[city].CloseCities.Count)];

}

else

{

// Otherwise, pick a completely random city.

nextCity = rand.Next(cityList.Count);

}

// Make sure we haven't been here, and make sure it isn't where we are at now.

} while ((tour[nextCity].Connection2 != -1) || (nextCity == lastCity));

// When going from city A to B, [1] on A = B and [1] on city B = A

tour[lastCity].Connection2 = nextCity;

tour[nextCity].Connection1 = lastCity;

lastCity = nextCity;

}

// Connect the last 2 cities.

tour[lastCity].Connection2 = firstCity;

tour[firstCity].Connection1 = lastCity;

tour.DetermineFitness(cityList);

Add(tour);

if ((bestTour == null) || (tour.Fitness < bestTour.Fitness))

{

BestTour = tour;

}

Program.cs

using System;

using System.Windows.Forms;

namespace Tsp

{

/// <summary>

/// Contains the Main that starts this form.

/// </summary>

static class Program

{

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new TspForm());

}

Tour.cs

using System;

using System.Collections.Generic;

using System.Text;

namespace Tsp

{

/// <summary>

/// This class represents one instance of a tour through all the cities.

/// </summary>

public class Tour : List<Link>

{

/// <summary>

/// Constructor that takes a default capacity.

/// </summary>

/// <param name="capacity">Initial size of the tour. Should be the number of cities in the tour.</param>

public Tour(int capacity)

: base(capacity)

{

resetTour(capacity);

}

/// <summary>

/// Private copy of this fitness of this tour.

/// </summary>

private double fitness;

/// <summary>

/// The fitness (total tour length) of this tour.

/// </summary>

public double Fitness

{

set

{

fitness = value;

}

get

{

return fitness;

}

/// <summary>

/// Creates the tour with the correct number of cities and creates initial connections of all -1.

/// </summary>

/// <param name="numberOfCities"></param>

private void resetTour(int numberOfCities)

{

this.Clear();

Link link;

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

{

link = new Link();

link.Connection1 = -1;

link.Connection2 = -1;

this.Add(link);

}

/// <summary>

/// Determine the fitness (total length) of an individual tour.

/// </summary>

/// <param name="cities">The cities in this tour. Used to get the distance between each city.</param>

public void DetermineFitness(Cities cities)

{

Fitness = 0;

int lastCity = 0;

int nextCity = this[0].Connection1;

foreach (Link link in this)

{

Fitness += cities[lastCity].Distances[nextCity];

// figure out if the next city in the list is [0] or [1]

if (lastCity != this[nextCity].Connection1)

{

lastCity = nextCity;

nextCity = this[nextCity].Connection1;

}

else

{

lastCity = nextCity;

nextCity = this[nextCity].Connection2;

}

/// <summary>

/// Creates a link between 2 cities in a tour, and then updates the city usage.

/// </summary>

/// <param name="tour">The incomplete child tour.</param>

/// <param name="cityUsage">Number of times each city has been used in this tour. Is updated when cities are joined.</param>

/// <param name="city1">The first city in the link.</param>

/// <param name="city2">The second city in the link.</param>

private static void joinCities(Tour tour, int[] cityUsage, int city1, int city2)

{

// Determine if the [0] or [1] link is available in the tour to make this link.

if (tour[city1].Connection1 == -1)

{

tour[city1].Connection1 = city2;

}

else

{

tour[city1].Connection2 = city2;

}

if (tour[city2].Connection1 == -1)

{

tour[city2].Connection1 = city1;

}

else

{

tour[city2].Connection2 = city1;

}

cityUsage[city1]++;

cityUsage[city2]++;

}

/// <summary>

/// Find a link from a given city in the parent tour that can be placed in the child tour.

/// If both links in the parent aren't valid links for the child tour, return -1.

/// </summary>

/// <param name="parent">The parent tour to get the link from.</param>

/// <param name="child">The child tour that the link will be placed in.</param>

/// <param name="cityList">The list of cities in this tour.</param>

/// <param name="cityUsage">Number of times each city has been used in the child.</param>

/// <param name="city">City that we want to link from.</param>

/// <returns>The city to link to in the child tour, or -1 if none are valid.</returns>

private static int findNextCity(Tour parent, Tour child, Cities cityList, int[] cityUsage, int city)

{

if (testConnectionValid(child, cityList, cityUsage, city, parent[city].Connection1))

{

return parent[city].Connection1;

}

else if (testConnectionValid(child, cityList, cityUsage, city, parent[city].Connection2))

{

return parent[city].Connection2;

}

return -1;

}

/// <summary>

/// Determine if it is OK to connect 2 cities given the existing connections in a child tour.

/// If the two cities can be connected already (witout doing a full tour) then it is an invalid link.

/// </summary>

/// <param name="tour">The incomplete child tour.</param>

/// <param name="cityList">The list of cities in this tour.</param>

/// <param name="cityUsage">Array that contains the number of times each city has been linked.</param>

/// <param name="city1">The first city in the link.</param>

/// <param name="city2">The second city in the link.</param>

/// <returns>True if the connection can be made.</returns>

private static bool testConnectionValid(Tour tour, Cities cityList, int[] cityUsage, int city1, int city2)

{

// Quick check to see if cities already connected or if either already has 2 links

if ((city1 == city2) || (cityUsage[city1] == 2) || (cityUsage[city2] == 2))

{

return false;

}

// A quick check to save CPU. If haven't been to either city, connection must be valid.

if ((cityUsage[city1] == 0) || (cityUsage[city2] == 0))

{

return true;

}

// Have to see if the cities are connected by going in each direction.

for (int direction = 0; direction < 2; direction++)

{

int lastCity = city1;

int currentCity;

if (direction == 0)

{

currentCity = tour[city1].Connection1; // on first pass, use the first connection

}

else

{

currentCity = tour[city1].Connection2; // on second pass, use the other connection

}

int tourLength = 0;

while ((currentCity != -1) && (currentCity != city2) && (tourLength < cityList.Count - 2))

{

tourLength++;

// figure out if the next city in the list is [0] or [1]

if (lastCity != tour[currentCity].Connection1)

{

lastCity = currentCity;

currentCity = tour[currentCity].Connection1;

}

else

{

lastCity = currentCity;

currentCity = tour[currentCity].Connection2;

}

// if cities are connected, but it goes through every city in the list, then OK to join.

if (tourLength >= cityList.Count - 2)

{

return true;

}

// if the cities are connected without going through all the cities, it is NOT OK to join.

if (currentCity == city2)

{

return false;

}

// if cities weren't connected going in either direction, we are OK to join them

return true;

}

/// <summary>

/// Perform the crossover operation on 2 parent tours to create a new child tour.

/// This function should be called twice to make the 2 children.

/// In the second call, the parent parameters should be swapped.

/// </summary>

/// <param name="parent1">The first parent tour.</param>

/// <param name="parent2">The second parent tour.</param>

/// <param name="cityList">The list of cities in this tour.</param>

/// <param name="rand">Random number generator. We pass around the same random number generator, so that results between runs are consistent.</param>

/// <returns>The child tour.</returns>

public static Tour Crossover(Tour parent1, Tour parent2, Cities cityList, Random rand)

{

Tour child = new Tour(cityList.Count); // the new tour we are making

int[] cityUsage = new int[cityList.Count]; // how many links 0-2 that connect to this city

int city; // for loop variable

int nextCity; // the other city in this link

for (city = 0; city < cityList.Count; city++)

{

cityUsage[city] = 0;

}

// Take all links that both parents agree on and put them in the child

for (city = 0; city < cityList.Count; city++)

{

if (cityUsage[city] < 2)

{

if (parent1[city].Connection1 == parent2[city].Connection1)

{

nextCity = parent1[city].Connection1;

if (testConnectionValid(child, cityList, cityUsage, city, nextCity))

{

joinCities(child, cityUsage, city, nextCity);

}

if (parent1[city].Connection2 == parent2[city].Connection2)

{

nextCity = parent1[city].Connection2;

if (testConnectionValid(child, cityList, cityUsage, city, nextCity))

{

joinCities(child, cityUsage, city, nextCity);

}

if (parent1[city].Connection1 == parent2[city].Connection2)

{

nextCity = parent1[city].Connection1;

if (testConnectionValid(child, cityList, cityUsage, city, nextCity))

{

joinCities(child, cityUsage, city, nextCity);

}

if (parent1[city].Connection2 == parent2[city].Connection1)

{

nextCity = parent1[city].Connection2;

if (testConnectionValid(child, cityList, cityUsage, city, nextCity))

{

joinCities(child, cityUsage, city, nextCity);

}

// The parents don't agree on whats left, so we will alternate between using

// links from parent 1 and then parent 2.

for (city = 0; city < cityList.Count; city++)

{

if (cityUsage[city] < 2)

{

if (city % 2 == 1) // we prefer to use parent 1 on odd cities

{

nextCity = findNextCity(parent1, child, cityList, cityUsage, city);

if (nextCity == -1) // but if thats not possible we still go with parent 2

{

nextCity = findNextCity(parent2, child, cityList, cityUsage, city); ;

}

else // use parent 2 instead

{

nextCity = findNextCity(parent2, child, cityList, cityUsage, city);

if (nextCity == -1)

{

nextCity = findNextCity(parent1, child, cityList, cityUsage, city);

}

if (nextCity != -1)

{

joinCities(child, cityUsage, city, nextCity);

// not done yet. must have been 0 in above case.

if (cityUsage[city] == 1)

{

if (city % 2 != 1) // use parent 1 on even cities

{

nextCity = findNextCity(parent1, child, cityList, cityUsage, city);

if (nextCity == -1) // use parent 2 instead

{

nextCity = findNextCity(parent2, child, cityList, cityUsage, city);

}

else // use parent 2

{

nextCity = findNextCity(parent2, child, cityList, cityUsage, city);

if (nextCity == -1)

{

nextCity = findNextCity(parent1, child, cityList, cityUsage, city);

}

if (nextCity != -1)

{

joinCities(child, cityUsage, city, nextCity);

}

// Remaining links must be completely random.

// Parent's links would cause multiple disconnected loops.

for (city = 0; city < cityList.Count; city++)

{

while (cityUsage[city] < 2)

{

nextCity = rand.Next(cityList.Count); // pick a random city, until we find one we can link to

} while (!testConnectionValid(child, cityList, cityUsage, city, nextCity));

joinCities(child, cityUsage, city, nextCity);

}

return child;

}

/// <summary>

/// Randomly change one of the links in this tour.

/// </summary>

/// <param name="rand">Random number generator. We pass around the same random number generator, so that results between runs are consistent.</param>

public void Mutate(Random rand)

{

int cityNumber = rand.Next(this.Count);

Link link = this[cityNumber];

int tmpCityNumber;

// Find which 2 cities connect to cityNumber, and then connect them directly

if (this[link.Connection1].Connection1 == cityNumber) // Conn 1 on Conn 1 link points back to us.

{

if (this[link.Connection2].Connection1 == cityNumber)// Conn 1 on Conn 2 link points back to us.

{

tmpCityNumber = link.Connection2;

this[link.Connection2].Connection1 =link.Connection1;

this[link.Connection1].Connection1 = tmpCityNumber;

}

else // Conn 2 on Conn 2 link points back to us.

{

tmpCityNumber = link.Connection2;

this[link.Connection2].Connection2 = link.Connection1;

this[link.Connection1].Connection1 = tmpCityNumber;

}

else // Conn 2 on Conn 1 link points back to us.

{

if (this[link.Connection2].Connection1 == cityNumber)// Conn 1 on Conn 2 link points back to us.

{

tmpCityNumber = link.Connection2;

this[link.Connection2].Connection1 = link.Connection1;

this[link.Connection1].Connection2 = tmpCityNumber;

}

else // Conn 2 on Conn 2 link points back to us.

{

tmpCityNumber = link.Connection2;

this[link.Connection2].Connection2 = link.Connection1;

this[link.Connection1].Connection2 = tmpCityNumber;

}

int replaceCityNumber = -1;

{

replaceCityNumber = rand.Next(this.Count);

}

while (replaceCityNumber == cityNumber);

Link replaceLink = this[replaceCityNumber];

// Now we have to reinsert that city back into the tour at a random location

tmpCityNumber = replaceLink.Connection2;

link.Connection2 = replaceLink.Connection2;

link.Connection1 = replaceCityNumber;

replaceLink.Connection2 = cityNumber;

if (this[tmpCityNumber].Connection1 == replaceCityNumber)

{

this[tmpCityNumber].Connection1 = cityNumber;

}

else

{

this[tmpCityNumber].Connection2 = cityNumber;

}

Eventargs.cs

using System;

using System.Collections.Generic;

using System.Windows.Forms;

using System.Drawing;

namespace Tsp

{

/// <summary>

/// Event arguments when the TSP class wants the GUI to draw a tour.

/// </summary>

public class TspEventArgs : EventArgs

{

/// <summary>

/// Default Constructor.

/// </summary>

public TspEventArgs()

{

}

/// <summary>

/// Constructor that sets all the properties.

/// </summary>

/// <param name="cityList">The list of cities to draw.</param>

/// <param name="bestTour">The tour that connects all the cities.</param>

/// <param name="generation">Which generation is this.</param>

/// <param name="complete">Is this the last update before we are done.</param>

public TspEventArgs(Cities cityList, Tour bestTour, int generation, bool complete)

{

this.cityList = cityList;

this.bestTour = bestTour;

this.generation = generation;

this.complete = complete;

}

/// <summary>Private copy of the list of cities.</summary>

private Cities cityList;

/// <summary>Public property for list of cities.</summary>

public Cities CityList

{

get

{

return cityList;

}

/// <summary>Private copy of the tour of the cities.</summary>

private Tour bestTour;

/// <summary>Public property for the tour of the cities.</summary>

public Tour BestTour

{

get

{

return bestTour;

}

/// <summary>Private copy for which generation this tour came from.</summary>

private int generation;

/// <summary>Public property for which generation this tour came from.</summary>

public int Generation

{

get

{

return generation;

}

set

{

generation = value;

}

/// <summary>Private copy indicating if the TSP algorithm is complete.</summary>

private bool complete = false;

/// <summary>Public property indicating if the TSP algorithm is complete.</summary>

public bool Complete

{

get

{

return complete;

}

set

{

complete = value;

}

Графическое представление

Карта городов

Дата добавления: 2019-03-09; просмотров: 247; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!