Список работ

Применение генетического алгоритма в задаче коммивояжера

Содержание

Введение

В задаче коммивояжера ищется кратчайший маршрут между городами, которые коммивояжер должен посетить. В качестве начального может быть выбран любой город. Посетить нужно все заданные города и вернуться в стартовый город. Каждый город посещается единожды, кроме стартового, который коммивояжер посещает в начале и в конце пути.
Когда лучший маршрут найден, стартовым может быть любой его город.
Есть и иные трактовки задачи, например, найти маршрут с минимальной стоимостью.
Тривиальное решение – это перебор всех вариантов, однако такой подход не годится уже при небольшом числе посещаемых городов ввиду неприемлемых вычислительных затрат.
Простейшим решением является употребление жадного алгоритма, суть которого в том, что следующим выбирается город, ближайший к городу нахождения коммивояжера. В общем случае результат далек от оптимального.
В работе рассматривается возможность употребления генетического алгоритма для поиска хорошего решения.
Суть подхода в том, что прежде генерируется множество маршрутов. Это множество называется популяцией. Далее к маршрутам множества применяются операции скрещивания и мутации.
При скрещивании из двух выбранных маршрутов формируется в результате обмена участками маршрута дочерний маршрут.
При мутации меняются местами участки внутри ранее созданного дочернего маршрута.
Приводимый ниже код является модификацией программы, разработанной в 2006 г. Michael LaLena (см. www.lalena.com). Автор программы не возражает против ее некоммерческого использования третьими лицами, например в учебных целях.

Решения задачи коммивояжера

Основывается на генетическом алгоритме.

Интерфейс приложения

Программа содержит одну форму (рис. 1).

Решение найдено

Рис. 1. Форма приложения. Решение найдено

Форма имеет область графического вывода (карту) и позволяет:

Графическая область формы – это объект System.Windows.Forms.PictureBox с именем tourDiagram.
PictureBox может быть выбран и вставлен в форму, например, в результате выполнения следующей цепочки "View–Toolbox–CommonControls–PictureBox". Так же PictureBox можно обнаружить, выполнив "меню Tools–Choose Toolbox Items–вкладка .NET Framework Components–PictureBox".
Для графического вывода создаются следующие объекты:

Далее при выводе лучшего маршрута методами cityGraphics отображаются города в виде окружностей и участки маршрута в виде отрезков прямых линий (см. процедуры DrawTour и DrawCityList).
Визуализация образа выполняется объектом tourDiagram:

tourDiagram.Image = cityImage;

Формат XML- файла

XML-файл содержит перечень координат городов. При отображении на карте используется физическая система координат. Начало координат расположено в верхнем левом углу карты.
Данные в XML-файле должны быть указаны в следующем формате:

<?xml version="1.0" encoding="utf-8" ?>
<CitiesPos>
<CityPos X="160" Y="370"/>
<CityPos X="121" Y="132"/>

</CitiesPos>

При чтении файла, если нет ошибок, заполняется список городов, и они отображаются на карте (см. метод OpenCityList).
Элемент списка – это число из диапазона [0, cnt – 1], где cnt – это число городов в маршруте.

Модель маршрута

Маршрут представляется в виде списка tour номеров городов размера cnt + 1, где cnt - это число посещаемых коммивояжером городов. При этом первый город маршрута (списка) добавляется и в начало, и в конец списка. Это позволяет представить маршрут в виде цепочки городов (рис. 2).

Решение найдено

Рис. 2. Представление маршрута в виде цепочки городов. Первый и последний города совпадают: tour[0] = tour[cnt]

Лучший маршрут – это самая короткая цепочка.
Замечание. В программе Michael LaLena [1] использована более сложная модель маршрута: для каждого города указываются его сосед слева и сосед справа. Такая модель усложняет реализацию операций скрещивания и мутации.
Нетрудно заметить, что информация о соседях слева и справа каждого города присутствует и в приведенной на рис. 2 модели. Для первого и последнего городов маршрута (красного и желтого) эта проблема решена за счет дублирования в модели первого (красного) города маршрута.

Модель популяции

Популяция – это список маршрутов. Маршрут в списке представляется числом из диапазона [0, populationSize - 1], где populationSize – это размер популяции.
Размер списка постоянен, хотя это и необязательно. Скажем, в популяцию можно добавлять дочерний маршрут, а не заменять им, как это делается в программе, плохой (слишком длинный) маршрут популяции. Можно иметь процедуру чистки популяции, удаляющую время от времени из популяции плохие маршруты и т. д.
Перед созданием начальной популяции для каждого города определяется список closeCities городов-соседей, то есть городов, наиболее близко расположенных к текущему городу. Число городов-соседей у каждого города одинаково и равно numberOfCloseCities.
Элемент списка – это число из диапазона [0, cnt – 1], где cnt – число городов в маршруте. Города в списке упорядочены по возрастанию расстояний городов до текущего города.
Начальная популяция формируется следующим образом:

  1. Получить случайное число из диапазона [0, cnt – 1] и интерпретировать его как номер текущего города (cnt – число городов в маршруте).
  2. Получить случайное число из диапазона [0, 99], если оно меньше chanceUseCloseCity, то получить следующий город маршрута по принципу жадного алгоритма, то есть взять его из списка closeCities городов-соседей (берется первый свободный город списка). Если свободных, то есть не включенных в маршрут городов в списке соседей нет, то случайным образом берется свободный город из общего списка городов.
    Если случайное число более или равно chanceUseCloseCity, то в маршрут добавляется свободный город, случайно выбранный из общего списка городов.
  3. Передвинуть, сохраняя последовательность, в каждом маршруте города так, чтобы на первом месте оказался ранее заданный город cityNumber (в программе cityNumber = 0).
  4. Добавить в конец каждого маршрута его первый город (cityNumber).

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

Алгоритм

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

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

Промежуточные данные.

Алгоритм приводится без многих деталей. Их можно посмотреть в размещенном ниже коде программы.

  1. Загрузить в список cityList координаты всех городов либо из XML-файла (процедура openCityListButton_Click), либо ударяя мышкой по графической части формы (процедура tourDiagram_MouseDown), либо комбинируя первой и второе. Номер города – это индекс списка cityList.
  2. Найти и запомнить в списке Distances для каждого города расстояния до всех прочих городов (см. метод CalculateCityDistances класса Cities.)
  3. Найти и запомнить в списке CloseCities для каждого города номера его городов соседей, то есть наиболее близко расположенных к нему городов. Их число равно numberOfCloseCities (см. метод CalculateCityDistances класса Cities и метод FindClosestCities класса City).
  4. Сформировать начальную популяцию – список маршрутов, создаваемых на основе жадного алгоритма (см. метод CreateRandomPopulation класса Population).
  5. Рассчитать для каждого маршрута его длину (Fitness).
  6. generation = 0.
  7. Отобрать случайным образом из популяции population несколько (wrGroupSize) маршрутов и поместить их в рабочую группу – массив wrGroup.
  8. Упорядочить wrGroup по возрастанию длины маршрута (применяется пузырьковая сортировка).
  9. Взять два первых (лучших) маршрута массива wrGroup в качестве родительских и сформировать, используя скрещивание и мутацию, дочерний маршрут child (вероятность мутации задается параметром mutationChance).
  10. Заменить в популяции худший маршрут wrGroup на маршрут child.
  11. Вычислить длину маршрута child и если она меньше длины лучшего маршрута, то признать child в качестве лучшего маршрута. Отобразить новый лучший маршрут в графической части формы (процедура displayTour). Обновить также и информационные поля формы.
  12. generation = generation + 1.
  13. Если generation < maxGenerations, то перейти к п. 7 алгоритма, иначе завершить вычисления.

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

Классы приложения

В программе создаются следующие классы:

Особенности реализации

Поиск лучшего маршрута и отображение результата на карте городов выполняются в разных нитях.
Решение начинается после нажатия на кнопку "Пуск" (уже создан список городов cityList). Исполняется обработчик StartButton_Click. После выполнения проверок кнопка приобретает надпись "Стоп" и в отдельной нити запускается процедура BeginTsp:

ThreadPool.QueueUserWorkItem(new WaitCallback(BeginTsp));

Процедура BeginTsp после выполнения метода cityList.CalculateCityDistances и создания объекта tsp класса Tsp (tsp = new Tsp();)назначает событию tsp.foundNewBestTour процедуру tsp_foundNewBestTour, которую будет вызывать обработчик этого события. Далее запускается поиск решения: tsp.FindBestTour. После завершения вычислений tsp обнуляется (tsp = null;).

// Создает объект класса Tsp
// Выполняется в отдельной нити
private void BeginTsp(Object stateInfo)
{
 // Полагаем, что все данные введены корректно (проверяются в StartButton_Click)
 // Находим для каждого города расстояния до всех прочих городов, а также находим его соседей
 cityList.CalculateCityDistances(numberOfCloseCities);
 tsp = new Tsp();
 tsp.foundNewBestTour += new Tsp.NewBestTourEventHandler(tsp_foundNewBestTour);
 tsp.FindBestTour(populationSize, maxGenerations, wrGoupSize, mutationChance, seed, chanceUseCloseCity, cityList, numberOfCloseCities);
 tsp.foundNewBestTour -= new Tsp.NewBestTourEventHandler(tsp_foundNewBestTour);
 tsp = null;
}

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

Код приложения

Программа реализована на C# как Windows Form Application.

using System; // Random, InvalidCastException и пр.
using System.Windows.Forms; // PictureBox (tourDiagram), Application (см. класс class Program), MessageBox
using System.Collections.Generic; // Для List
using System.Data; // DataSet, DataRowCollection
using System.Drawing; // Image, Graphics, Point
using System.Threading; // ThreadPool
using System.IO; // FileNotFoundException

namespace Tsp
{
 // Класс TspForm управляет формой приложения
 public partial class TspForm : Form
 {
  public int populationSize = 0; // Размер популяции
  public int maxGenerations = 0; // Предельное число поколений
  public int mutationChance = 0; // Вероятность мутации дочернего маршрута
  public int wrGoupSize = 0; // Размер рабочей группы
  public int numberOfCloseCities = 0; // Число городов-соседей любого города
  public int chanceUseCloseCity = 0; // Вероятность добавления в маршрут города из списка городов-соседей
  public int seed = 0; // Затравка датчика случайных чисел
  // Список городов, которые должен посетить коммивояжер
  Cities cityList = new Cities();
  // Tsp – класс, реализующий генетическиий алгоритм решения задачи коммивояжера (tsp-алгоритм)
  // Если tsp не null, то задача выполняется
  Tsp tsp;
  // Образ для отображения городов и маршрута
  public Image cityImage;
  // Графический объект для образа cityImage
  public Graphics cityGraphics;
  // Используется отдельная нить, чтобы обновлять карту городов во время вычислений
  public delegate void DrawEventHandler(Object sender, TspEventArgs e);
  // Стандартный конструктор
  public TspForm()
  {
   InitializeComponent();
  }
  // tsp-алгоритм порождает событие foundNewBestTour при нахождении текущего лучшего маршрута
  // При этом оживляется GUI-нить, что позволяет обновить карту городов
  private void tsp_foundNewBestTour(object sender, TspEventArgs e)
  {
   if (this.InvokeRequired)
   {
    try
    {
     this.Invoke(new DrawEventHandler(DrawTour), new object[] { sender, e });
     return;
    }
    catch (Exception) { } // Неудача
   }
   // Отображаем маршрут
   DrawTour(sender, e);
  }
  // Отображает последний лучший маршрут
  // и обновляет поля с числом итераций, длиной маршрута и числом улучшений решения
  public void DrawTour(object sender, TspEventArgs e)
  {
   Tour bestTour = e.BestTour; // Лучший маршрут
   cityList = e.CityList;
   this.lastFitnessValue.Text = Math.Round(bestTour.Fitness, 2).ToString();
   this.lastIterationValue.Text = e.Generation.ToString();
   this.NumberOfImprv.Text = e.Imprv.ToString();
   int city = bestTour[0];
   int nextCity;
   cityGraphics.FillRectangle(Brushes.White, 0, 0, cityImage.Width, cityImage.Height);
   Point pos;
   int cTour = bestTour.Count;
   for (int step = 1; step < cTour; step++)
   {
    pos = cityList[city].Location;
    nextCity = bestTour[step];
    city = nextCity;
    // Отображаем город в виде окружности
    // Начальный город маршрута заливаем красным цветом, второй – синим, последний – желтым
    if (step == 1) // Окружность начального города маршрута заливаем красным цветом
    {
     cityGraphics.FillEllipse(Brushes.Red, pos.X - 5, pos.Y - 5, 10, 10);
    }
    else if (step == 2) // Окружность второго города маршрута заливаем синим цветом
    {
     cityGraphics.FillEllipse(Brushes.Blue, pos.X - 5, pos.Y - 5, 10, 10);
    }
    else if (step == cTour - 1) // Окружность предпоследнего города маршрута заливаем желтым цветом
    {
     cityGraphics.FillEllipse(Brushes.Gold, pos.X - 5, pos.Y - 5, 10, 10);
    }
    else
    {
     cityGraphics.DrawEllipse(Pens.Black, pos.X - 3, pos.Y - 3, 6, 6);
    }
    // Соединяем 2 города линией
    cityGraphics.DrawLine(Pens.Black, pos, cityList[nextCity].Location);
   }
   tourDiagram.Image = cityImage;
   if (e.Done)
   {
    StartButton.Text = "Пуск";
    StatusLabel.Text = "Откройте XML или укажите города на карте мышкой";
    StatusLabel.ForeColor = Color.Black;
   }
  }
  // Отображает города на растровой карте
  private void DrawCityList(Cities cityList)
  {
   cityImage = new Bitmap(tourDiagram.Width, tourDiagram.Height);
   cityGraphics = Graphics.FromImage(cityImage);
   foreach (City city in cityList)
   {
    // Город в виде окружностии
    cityGraphics.DrawEllipse(Pens.Black, city.Location.X - 3, city.Location.Y - 3, 6, 6);
   }
   this.tourDiagram.Image = cityImage;
   // Обновляем в форме текстовое поле с числом городов
   this.NumberCitiesValue.Text = cityList.Count.ToString();
  }
  // Запускает или останавливает решение задачи коммивояжера
  private void StartButton_Click(object sender, EventArgs e)
  {
   // Останавливаем нить tsp, если задача решается
   if (tsp != null)
   {
    tsp.Halt = true;
    return;
   }
   try
   {
    populationSize = Convert.ToInt32(populationSizeTextBox.Text);
    maxGenerations = Convert.ToInt32(maxGenerationTextBox.Text);
    mutationChance = Convert.ToInt32(mutationTextBox.Text);
    wrGoupSize = Convert.ToInt32(groupSizeTextBox.Text);
    numberOfCloseCities = Convert.ToInt32(NumberCloseCitiesTextBox.Text);
    chanceUseCloseCity = Convert.ToInt32(CloseCityOddsTextBox.Text);
    seed = Convert.ToInt32(randomSeedTextBox.Text);
   }
   catch (FormatException)
   {
    MessageBox.Show("В полях ввода должны быть числа", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
    return;
   }
   string show = "";
   bool ok = true;
   if (cityList.Count == 0)
   {
    show = "Список городов пуст"; ok = false;
   }
   if (ok && cityList.Count < 5)
   {
    show = "Число городов не может быть меньше, чем 5"; ok = false;
   }
   if (ok && populationSize <= 0)
   {
    show = "Укажите размер популяции"; ok = false;
   }
   if (ok && maxGenerations <= 0)
   {
    show = "Задайте максимальное число поколений"; ok = false;
   }
   if (ok && ((mutationChance < 0) || (mutationChance > 100)))
   {
    show = "Число мутаций должно быть между 0 и 100"; ok = false;
   }
   if (ok && ((wrGoupSize < 2) || (wrGoupSize > populationSize)))
   {
    show = "Размер рабочей группы задается между 2 и размером популяций"; ok = false;
   }
   if (ok && ((numberOfCloseCities < 3) || (numberOfCloseCities >= cityList.Count)))
   {
    show = "Число городов-соседей для создания начальной популяции должно быть между 3 и числом городов"; ok = false;
   }
   if (ok && ((chanceUseCloseCity < 0) || (chanceUseCloseCity > 100)))
   {
    show = "Вероятность использования города-соседа при создании начальной популяции лежит между 0 и 100"; ok = false;
   }
   if (ok && seed < 0)
   {
    show = "Затравка датчика случайных чисел не может быть менее нуля"; ok = false;
   }
   if (!ok)
   {
    MessageBox.Show(show, "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
    return;
   }
   this.StartButton.Text = "Стоп";
   ThreadPool.QueueUserWorkItem(new WaitCallback(BeginTsp));
  }
  // Создает объект класса Tsp
  // Выполняется в отдельной нити
  private void BeginTsp(Object stateInfo)
  {
   // Полагаем, что все данные введены корректно (проверяются в StartButton_Click)
   // Находим для каждого города расстояния до всех прочих городов, а также находим его соседей
   cityList.CalculateCityDistances(numberOfCloseCities);
   tsp = new Tsp();
   tsp.foundNewBestTour += new Tsp.NewBestTourEventHandler(tsp_foundNewBestTour);
   tsp.FindBestTour(populationSize, maxGenerations, wrGoupSize, mutationChance, seed, chanceUseCloseCity, cityList, numberOfCloseCities);
   tsp.foundNewBestTour -= new Tsp.NewBestTourEventHandler(tsp_foundNewBestTour);
   tsp = null;
  }
  // Выбирает XML-файл с координатами городов
  private void selectFileButton_Click(object sender, EventArgs e)
  {
   OpenFileDialog fileOpenDialog = new OpenFileDialog();
   fileOpenDialog.Filter = "XML(*.xml)|*.xml";
   fileOpenDialog.InitialDirectory = ".";
   fileOpenDialog.ShowDialog();
   fileNameTextBox.Text = fileOpenDialog.FileName;
  }
  // Формируем список городов по XML-файлу
  private void openCityListButton_Click(object sender, EventArgs e)
  {
   string fileName = "";
   try
   {
    if (tsp != null)
    {
     StatusLabel.Text = "Нельзя изменять список городов во время работы алгоритма";
     StatusLabel.ForeColor = Color.Red;
     return;
    }
    fileName = this.fileNameTextBox.Text;
    // Читаем файл и формируем список городов
    cityList.OpenCityList(fileName);
    // Отображаем горрода на карте
    this.DrawCityList(cityList);
   }
   catch (FileNotFoundException)
   {
    MessageBox.Show("Файл не найден: " + fileName, "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
   }
   catch (InvalidCastException)
   {
    MessageBox.Show("Плохой формат XML-файла", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
   }
   catch
   {
    MessageBox.Show("Не выбран файл", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
   }
  }
  private bool stillRun()
  {
   if (tsp != null) // Если выполнянется поиск решения
   {
    StatusLabel.Text = "Нельзя изменять список городов во время работы алгоритма";
    StatusLabel.ForeColor = Color.Red;
    return true;
   }
   return false;
  }
  // Очистка списка городов
  private void clearCityListButton_Click(object sender, EventArgs e)
  {
   if (stillRun()) return;
   cityList.Clear();
   this.DrawCityList(cityList);
  }
  // Размещает город на карте в точке мышиного удара
  private void tourDiagram_MouseDown(object sender, MouseEventArgs e)
  {
   if (stillRun()) return;
   cityList.Add(new City(e.X, e.Y)); // e.X, e.Y - координаты мыши в физической системе координат
   this.DrawCityList(cityList);
  }
 }
 // Класс Program предоставляет метод Main для точки входа (entry point)
 static class Program
 {
  [STAThread] // Точка входа приложения
  static void Main()
  {
   Application.Run(new TspForm());
  }
 }
 // Класс TspEventArgs устанавливает аргументы события, при наступлении которого отображается очередной лучший маршрут
 public class TspEventArgs : EventArgs
 {
  // Конструктор, устанавливающий значения свойств события
  public TspEventArgs(Cities cityList, Tour bestTour, int generation, bool done, int imprv)
  {
   this.cityList = cityList; // Список городов
   this.bestTour = bestTour; // Лучший маршрут
   this.generation = generation; // Номер поколения
   this.done = done; // Флаг завершения алгоритма
   this.imprv = imprv; // Число улучшений решения
  }
  // Список городов (private копия и public)
  private Cities cityList;
  public Cities CityList
  {
   get
   {
    return cityList;
   }
  }
  // Лучший маршрут (private копия и public)
  private Tour bestTour;
  public Tour BestTour
  {
   get
   {
    return bestTour;
   }
  }
  // Номер поколения, в котором появился текущий лучший маршрут (private копия и public)
  private int generation;
  public int Generation
  {
   get
   {
    return generation;
   }
   set
   {
    generation = value;
   }
  }
  // Флаг завершения алгоритма (private копия и public)
  private bool done = false;
  public bool Done
  {
   get
   {
    return done;
   }
   set
   {
    done = value;
   }
  }
  // Число улучшений маршрута (private копия и public)
  private int imprv;
  public int Imprv
  {
   get
   {
    return imprv;
   }
   set
   {
    imprv = value;
   }
  }
 }
 // Класс City обеспечивает формирование и хранение позиции города (свойство Location),
 // хранение в списке Distances расстояний от текущего города до всех прочих городов,
 // формирование (метод FindClosestCities) и хранение списка CloseCities городов-соседей текущего города
 public class City
 {
  // Конструктор, обеспечивающий формирование позиции города
  public City(int x, int y)
  {
   Location = new Point(x, y); // System.Drawing.Point class
  }
  // Позиция города (private копия и public)
  private Point location;
  public Point Location
  {
   get
   {
    return location;
   }
   set
   {
    location = value;
   }
  }
  // Расстояния от города до каждого из прочих городов (private копия и public)
  // Индекс списка - это номер соответствующего города
  private List<double> distances = new List<double>();
  public List<double> Distances
  {
   get
   {
    return distances;
   }
   set
   {
    distances = value;
   }
  }
  // Список городов-соседей (private копия и public)
  private List<int> closeCities = new List<int>();
  public List<int> CloseCities
  {
   get
   {
    return closeCities;
   }
  }
  // Находит для текущего города его города-соседи (их число равно numberOfCloseCities)
  // Помещает их в список closeCities
  public void FindClosestCities(int numberOfCloseCities)
  {
   double shortestDistance;
   int shortestCity = 0;
   int dCnt = Distances.Count;
   double[] dist = new double[dCnt];
   // Копируем список расстояний города до прочих городов в массив dist
   Distances.CopyTo(dist);
   closeCities.Clear();
   for (int i = 0; i < numberOfCloseCities; i++)
   {
    shortestDistance = Double.MaxValue;
    for (int city = 0; city < dCnt; city++)
    {
     if (dist[city] < shortestDistance)
     {
      shortestDistance = dist[city];
      shortestCity = city;
     }
    }
    closeCities.Add(shortestCity);
    dist[shortestCity] = Double.MaxValue;
   }
  }
 }
 // Класс Cities содержит список городов
 // Для каждого города указываются его координаты, расстояния до каждого прочего города и список городов-соседей
 public class Cities : List<City>
 {
  // Находит и помещает в список city.Distances расстояния от выбранного города до всех прочих городов
  // Находит для каждого города его numberOfCloseCities городов-соседей и помещает их в список closeCities
  public void CalculateCityDistances(int numberOfCloseCities)
  {
   foreach (City city in this)
   {
    city.Distances.Clear();
    Point pos = city.Location;
    for (int i = 0; i < Count; i++)
    {
     Point pos2 = this[i].Location;
     city.Distances.Add(Math.Sqrt(Math.Pow((double)(pos.X - pos2.X), 2D) + Math.Pow((double)(pos.Y - pos2.Y), 2D)));
    }
   }
   foreach (City city in this)
   {
    // Находим для каждого города его numberOfCloseCities соседей
    city.FindClosestCities(numberOfCloseCities);
   }
  }
  // Формирует список городов по данным XML-файла
  // Исключения:
  // плохой формат XML-файла
  // не задано имя XML-файла
  // плохое имя файла (пара метр fileName)
  // Фрагмент XML-файла
  // <?xml version="1.0" encoding="utf-8" ?>
  // <CitiesPos>
  //  <CityPos X="121" Y="132"/>
  //  <CityPos X="160" Y="370"/>
  //  ...
  // </CitiesPos>
  public void OpenCityList(string fileName)
  {
   DataSet cityDS = new DataSet();
   try
   {
    this.Clear();
    cityDS.ReadXml(fileName);
    // Коллекция строк с координатами городов; X и Y - имена атрибутов тега City
    DataRowCollection cities = cityDS.Tables[0].Rows;
    foreach (DataRow city in cities)
    {
     this.Add(new City(Convert.ToInt32(city["X"]), Convert.ToInt32(city["Y"]))); // или city[0], city[1]
    }
   }
   finally
   {
    cityDS.Dispose();
   }
  }
 }
  // Класс Population обеспечивает формирование начальной популяции
 class Population : List<Tour>
 {
  // Лучший маршрут (private-копия и public), найденный генетическим алгоритмом
  private Tour bestTour = null;
  public Tour BestTour
  {
   set
   {
    bestTour = value;
   }
   get
   {
    return bestTour;
   }
  }
  // Число улучшений решения (private-копия и public)
  private int imprv = 0;
  public int Imprv
  {
   set
   {
    imprv = value;
   }
   get
   {
    return imprv;
   }
  }
  // Формирует популяцию - начальный набор случайных маршрутов
  // populationSize - число создаваемых маршрутов (размер популяции)
  // cityList - список городов
  // rand - генератор случайных чисел. Обеспечивает различные результаты при запусках
  // chanceToUseCloseCity - вероятность выбора города из списка городов-соседей
  // numberOfCloseCities - число городов-соседей
  public void CreateRandomPopulation(int populationSize, Cities cityList, Random rand, int chanceToUseCloseCity, int numberOfCloseCities)
  {
   int cCnt = cityList.Count; // Число городов
   // В маршруте на один город больше
   // Формируется цепочка городов, в которой первый и последний города совпадают
   int tCnt = cCnt + 1;
   int city, cCity, nextCity;
   int tourCount;
   int step; // Номер участка маршрута
   bool[] cityUsage = new bool[cCnt]; // Список городов, не включенных в маршрут (свободных городов)
   List<int> cities = new List<int>();
   Tour tourTmp, tour;
   // Можно ввести параметр "Начальный город маршрутов" или положить cityNumber = rand.Next(cCnt)
   int cityNumber = 0; // Все маршруты в итоге будут начинаться с города cityNumber
   for (tourCount = 0; tourCount < populationSize; tourCount++)
   {
    for (city = 0; city < cCnt; city++)
    {
     cities.Add(city);
     cityUsage[city] = false; // true, если город city уже включен в маршрут
    }
    tourTmp = new Tour(cCnt);
    cCity = rand.Next(cCnt); // Город, добавляемый в маршрут
    tourTmp[0] = cCity; // Первый город маршрута
    cityUsage[cCity] = true; // Город с номером cCity включен в маршрут
    cities.Remove(cCity); // Удаляем город из списка свободных городов
    nextCity = cCity;
    for (step = 1; step < cCnt; step++)
    {
     // Подбираем следующий город маршрута
     if (rand.Next(100) < chanceToUseCloseCity)
     {
      // Берем первый свободный город из списка городов-соседей
      for (city = 0; city < numberOfCloseCities; city++)
      {
       nextCity = cityList[cCity].CloseCities[city];
       if (!cityUsage[nextCity]) break;
      }
     }
     // Если город nextCity уже в маршруте, то берем город из списка городов, не включенных в маршрут
     if (cityUsage[nextCity])
     {
      nextCity = cities[rand.Next(cities.Count)];
     }
     cityUsage[nextCity] = true;
     tourTmp[step] = nextCity; // Включаем город с номером nextCity в маршрут
     cities.Remove(nextCity);
     cCity = nextCity;
    }
    tour = new Tour(tCnt);
    if (tourTmp[0] == cityNumber)
    {
     for (step = 0; step < cCnt; step++)
     {
      tour[step] = tourTmp[step];
     }
    }
    else
    {
    // Ищем позицию города с номером cityNumber
     int city0 = 0, m = -1, n = 0;
     for (step = 0; step < cCnt; step++)
     {
      if (tourTmp[step] == cityNumber)
      {
       city0 = step;
       break;
      }
     }
     // Ставим в маршруте tour на первое место город с номером cityNumber
     // и добавляем в tour города из tourTmp, расположенные после cityNumber
     for (step = city0 + 1; step < cCnt; step++)
     {
      m++;
      tour[m] = tourTmp[step];
     }
     // Добавляем в tour города из tourTmp, расположенные перед cityNumber
     for (step = 0; step < city0; step++)
     {
      n++;
      tour[m + n] = tourTmp[step];
     }
    }
    tour[cCnt] = cityNumber; // Первый и последний города маршрута совпадают
    // Вычисляем длину маршрута
    tour.DetermineFitness(cityList);
    // Добавляем маршрут в популяцию
    Add(tour);
    // Изменяем, если на то есть основание, информацию о лучшем маршруте
    if ((bestTour == null) || (tour.Fitness < bestTour.Fitness))
    {
     BestTour = tour;
    }
   }
  }
 }
 // Класс Tour представляет маршрут по всем городам
 public class Tour : List<int>
 {
  // Конструктор, принимающий параметр capacity
  // capacity - размер маршрута. Равен числу городов + 1
  // Начальный пустой маршрут
  public Tour(int capacity)
  {
   this.Clear();
   for (int i = 0; i < capacity; i++)
   {
    this.Add(-1);
   }
  }
  // Протяженность маршрута (private копия и public)
  private double fitness;
  public double Fitness
  {
   set
   {
    fitness = value;
   }
   get
   {
    return fitness;
   }
  }
  // Определяет общую протяженность маршрута
  // cities - список городов маршрута. Используется, чтобы получить расстояние между городами
  public void DetermineFitness(Cities cities)
  {
   this.Fitness = 0;
   for (int i = 0; i < this.Count - 1; i++)
   {
    this.Fitness += cities[this[i]].Distances[this[i + 1]];
   }
  }
  public static Tour Crossover(Tour parent1, Tour parent2, Cities cityList, Random rand)
  {
   int cCnt = cityList.Count;
   Tour child = new Tour(cCnt + 1);  // Новый (дочерний) маршрут
   int step;       // Номер участка маршрута
   // Первоначально дочерний маршрут совпадает с parent1
   // Первый и последний города дочернего маршрута совпадают, как и у всех прочих маршрутов    for (step = 0; step < cCnt + 1; step++)
   {
    child[step] = parent1[step];
   }
   for (int i = 0; i < 2; i++) // Можно ввести параметр "Число скрещиваний" (i < nChanges взамен i < 2)
   {
    // Можно ввести параметр "Длина куска при скрещивании"; сейчас – это кусок с тремя городами
    child = makeChange(child, parent2, rand, cCnt, 3);
   }
   return child;
  }
  // child - дочерний маршрут
  // parent2 - второй родительский маршрут (при мутации равен child)
  static Tour makeChange(Tour child, Tour parent2, Random rand, int cCnt, int nCts)
  {
   int step, step2, city, city2;
   List<int> cities = new List<int>(); // Удаляемые из child города
   List<int> cities2 = new List<int>(); // Добавляемые в child города
   List<int> cities3 = new List<int>(); // Города для восполнения child
   // nCts - протяженность заменяемого куска маршрута
   // Берем из parent2 кусок маршрута с nCts городами и заменяем симметричный кусок в дочернем маршруте
   // При мутации parent2 = child
   step2 = rand.Next(cCnt - nCts);
   while (step2 == 0) step2 = rand.Next(cCnt - nCts);
   for (step = step2; step < step2 + nCts; step++)
   {
    city = child[step];
    city2 = parent2[step];
    child[step] = city2;
    cities.Add(city); // Удаляемые из child города
    cities2.Add(city2); // Добавляемые в child города
    cities3.Add(city); // Города для восполнения child
   }
   // Исключаем из списков cities2 и cities3 города списка cities
   int k, k2;
   for (k = 0; k < nCts; k++)
   {
    city = cities[k];
    for (k2 = 0; k2 < cities2.Count; k2++)
    {
     if (cities2[k2] == city)
     {
      cities2.Remove(city);
      cities3.Remove(city);
      break;
     }
    }
   }
   // Находим в дочернем маршруте оставшиеся в списке cities2 города и заменяем их на города из списка cities3
   int clft = cities2.Count;
   for (k = 0; k < clft; k++)
   {
    city = cities2[k];
    for (step = 1; step < cCnt; step++)
    {
     if (child[step] == city)
     {
      city2 = cities3[rand.Next(cities3.Count)];
      child[step] = city2;
      cities3.Remove(city2);
      break;
     }
    }
   }
   return child;
  }
  // Мутация
  // Случаным образом меняем местами 2 города маршрута или 2 куска маршрута
  // child - дочерний маршрут
  // rand - генератор случайных чисел
  public static Tour Mutate(Tour child, Random rand)
  {
   int tCnt = child.Count - 1;
   // Можно добавить параметр flipCity - "Тип мутации"
   // Если flipCity = true, то перестановка городов, иначе перестановка кусков маршрута
   bool flipCity = true;
   int nMutations = 2;
   for (int i = 0; i < nMutations; i++) // Можно добавить параметр nMutations - "Число мутаций"
   {
    if (flipCity)
    {
     int step = 0, step2 = 0;
     while (step == 0) step = rand.Next(tCnt);
     while (step2 == 0 || step2 == step) step2 = rand.Next(tCnt);
     int city = child[step];
     child[step] = child[step2];
     child[step2] = city;
    }
    else
    {
     // Можно ввести параметр mtnPiece - "Длина куска маршрута при мутации"
     int mtnPiece = 3;
     child = makeChange(child, child, rand, tCnt, mtnPiece);
    }
   }
   return child;
  }
 }
 // Класс Tsp координирует решение задачи коммивояжера
 class Tsp
 {
  // Обработчик сообытия "Найден текущий лучший маршрут"
  // sender - объект, создавший событие
  // e - аргументы события. Параметр содержит информацию о лучших маршрутах
  public delegate void NewBestTourEventHandler(Object sender, TspEventArgs e);
  public event NewBestTourEventHandler foundNewBestTour;
  // Генератор случайных чисел
  Random rand;
  // Список городов. Используется для расчета расстояний между городами
  Cities cityList;
  // Список всех маршрутов
  Population population;
  // Флаг завершения работы алгоритма (поиска новых поколений) (private копия и public)
  private bool halt = false;
  public bool Halt
  {
   get
   {
    return halt;
   }
   set
   {
    halt = value;
   }
  }
  // Старт вычисленний (алгоритма)
  // populationSize - число случайных маршрутов, создаваемых до начала вычислений
  // maxGenerations - максимальное число скрещиваний
  // wrGoupSize - число маршрутов, проверяемых в каждом поколении. 2 первых берутся в качестве родительских маршрутов, чьи дочерние маршруты заменят 2 худших маршрута в группе
  // mutationChance - вероятность мутации дочернего маршрута
  // seed - затравка датчика случайных чисел
  // chanceToUseCloseCity - вероятность выбора города-соседа
  // cityList - список городов
  // numberOfCloseCities - число городов-соседей
  public void FindBestTour(int populationSize, int maxGenerations, int wrGoupSize, int mutationChance, int seed, int chanceToUseCloseCity, Cities cityList, int numberOfCloseCities)
  {
   rand = new Random(seed);
   this.cityList = cityList;
   population = new Population();
   population.CreateRandomPopulation(populationSize, cityList, rand, chanceToUseCloseCity, numberOfCloseCities);
   displayTour(population.BestTour, 0, false, 0);
   int generation;
   for (generation = 0; generation < maxGenerations; generation++)
   {
    if (Halt)
    {
     break; // по требованию GUI
    }
    makeChildren(wrGoupSize, mutationChance, generation);
   }
   displayTour(population.BestTour, generation, true, population.Imprv);
  }
  // Случайным образом выбирает из популяции группу маршрутов
  // После сортировки группы по возрастанию длины маршрута два первых рассматриваются как родительские маршруты
  // Они участвуют в скрещивании
  // Дочерний маршрут заменяет худший маршрут текущей рабочей групппы
  // wrGoupSize - размер рабочей группы (число маршрутов в группе)
  // mutationChance - вероятность мутации (в %) дочернего маршрута
  // generation - текущее поколение
  void makeChildren(int wrGoupSize, int mutationChance, int generation)
  {
   int[] wrGoup = new int[wrGoupSize]; // Рабочая группа
   int i;
   // Один и тот же маршрут может попасть в рабочую группу неоднократно
   for (i = 0; i < wrGoupSize; i++)
   {
    wrGoup[i] = rand.Next(population.Count);
   }
   // Пузырьковая сортировка массива wrGoup по возрастанию длины маршрута
   bool swapped = true;
   int pass = 1, hold; // pass - номер прохода
   while (swapped && pass < wrGoupSize)
   {
    swapped = false;
    for (i = 0; i < wrGoupSize - pass; i++)
    {
     if (population[wrGoup[i]].Fitness > population[wrGoup[i + 1]].Fitness)
     {
      swapped = true; // Обмен
      hold = wrGoup[i];
      wrGoup[i] = wrGoup[i + 1];
      wrGoup[i + 1] = hold;
     }
    }
    pass++;
   }
   bool fndBestTour = false;
   // Можно ввести параметр attempMax - "Число попыток улучшить популяцию"
   int attemps = 0, attempMax = 1;
   while (!fndBestTour && attemps < attempMax)
   {
    attemps++;
    // 0, 1 - индексы массива wrGoup. Элементы массива wrGoup с этими индексами - это родительские маршруты
    fndBestTour = makeAChild(wrGoup, mutationChance, 0, 1, wrGoupSize - 1, fndBestTour);
    // Меняем родительские маршруты местами
    if (!fndBestTour) fndBestTour = makeAChild(wrGoup, mutationChance, 1, 0, wrGoupSize - 2, fndBestTour);
   }
   if (fndBestTour) displayTour(population.BestTour, generation, false, population.Imprv);
  }
  // wrGoup - рабочая группа маршрутов
  // p1 - индекс первого родительского маршрута в wrGoup
  // p2 - индекс второго родительского маршрута в wrGoup
  // bad - индекс заменяемого (плохого) маршрута в wrGoup
  // fndBestTour - равен true, если в результате скрещивания и мутации получен новый лучший маршрут
  bool makeAChild(int[] wrGoup, int mutationChance, int p1, int p2, int bad, bool fndBestTour)
  {
   int badTour = wrGoup[bad]; // badTour - индекс плохого маршрута в списке population
   // Скрещиваем два лучших маршрута рабочей группы. Результат - это дочерний маршрут
   // При выполнении условия rand.Next(100) < mutationChance применяем операцию мутации
   // Заменяем результатом последний или предпоследний маршрут этой группы (в списке population находится в позиции badTour)
   Tour child = Tour.Crossover(population[wrGoup[p1]], population[wrGoup[p2]], cityList, rand);
   // Мутация дочернего маршрута
   if (rand.Next(100) < mutationChance) child = Tour.Mutate(child, rand);
   // Находим длину дочернего маршрута
   child.DetermineFitness(cityList);
   // Проверяем, имеет ли дочерний маршрут наименьшую длину
   if (child.Fitness < population.BestTour.Fitness)
   {
    fndBestTour = true; // Найден текущий лучший маршрут
    population.BestTour = child;
    population.Imprv++; // Число улучшений решения
   }
   // Можно ввести параметр takeIfBetter – "Брать только улучшающй дочерний маршрут"
   bool takeIfBetter = false;
   if (takeIfBetter)
   {
    if (child.Fitness < population[badTour].Fitness) population[badTour] = child;
   }
   else
   {
    population[badTour] = child;
   }
   return fndBestTour;
  }
  // Порождает событите, воспринимаемое GUI, отображающим маршрут
  // bestTour - лучший на текущей момент маршрут
  // generationNumber - число порожденных поколений
  // done - если true, то вычисления завершаются
  // imprv - число улучшений решения
  void displayTour(Tour bestTour, int generationNumber, bool done, int imprv)
  {
   this.foundNewBestTour(this, new TspEventArgs(cityList, bestTour, generationNumber, done, imprv));
  }
 }
}

Заключение

В приведенной программе указаны возможности введения дополнительных управляющих параметров:

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

Ниже приведено содержимое файла CitiesPos.xml с координатами городов; маршрут, найденный для этих городов, показан на рис. 1.

<?xml version="1.0" encoding="utf-8" ?>
<CitiesPos>
  <CityPos X="160" Y="370"/>
  <CityPos X="121" Y="132"/>
  <CityPos X="58" Y="234"/>
  <CityPos X="41" Y="213"/>
  <CityPos X="143" Y="86"/>
  <CityPos X="312" Y="176"/>
  <CityPos X="121" Y="264"/>
  <CityPos X="231" Y="366"/>
  <CityPos X="380" Y="62"/>
  <CityPos X="202" Y="260"/>
  <CityPos X="241" Y="12"/>
  <CityPos X="23" Y="356"/>
  <CityPos X="43" Y="317"/>
  <CityPos X="175" Y="134"/>
  <CityPos X="260" Y="125"/>
  <CityPos X="277" Y="370"/>
  <CityPos X="312" Y="153"/>
  <CityPos X="23" Y="256"/>
  <CityPos X="313" Y="297"/>
  <CityPos X="131" Y="96"/>
  <CityPos X="87" Y="67"/>
  <CityPos X="249" Y="283"/>
  <CityPos X="307" Y="234"/>
  <CityPos X="159" Y="167"/>
  <CityPos X="285" Y="123"/>
  <CityPos X="12" Y="34"/>
  <CityPos X="85" Y="356"/>
  <CityPos X="387" Y="125"/>
  <CityPos X="135" Y="268"/>
  <CityPos X="185" Y="345"/>
  <CityPos X="75" Y="314"/>
  <CityPos X="275" Y="45"/>
  <CityPos X="313" Y="78"/>
  <CityPos X="110" Y="67"/>
  <CityPos X="256" Y="215"/>
  <CityPos X="314" Y="164"/>
  <CityPos X="342" Y="186"/>
  <CityPos X="331" Y="214"/>
  <CityPos X="141" Y="275"/>
  <CityPos X="67" Y="369"/>
</CitiesPos>

Источник

1. MichaelLaLena. www.lalena.com, 2006 г.

Список работ

Рейтинг@Mail.ru