-
Notifications
You must be signed in to change notification settings - Fork 2
/
Population.cs
98 lines (88 loc) · 4.19 KB
/
Population.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//////////////////////////////////////////////////////////////////////////////////////////////////
// File Name: Population.cs
// Permission to use, copy, modify, and distribute this Program and its documentation,
// if any, for any purpose and without fee is hereby granted, provided that:
// (i) you not charge any fee for the Program, and the Program not be incorporated
// by you in any software or code for which compensation is expected or received;
// (ii) the copyright notice listed above appears in all copies;
// (iii) both the copyright notice and this Agreement appear in all supporting documentation; and
// (iv) the name of Michael LaLena or lalena.com not be used in advertising or publicity
// pertaining to distribution of the Program without specific, written prior permission.
///////////////////////////////////////////////////////////////////////////////////////////////////
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++)
{
do
{
// 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;
}
}
}
}
}