使用遗传算法解决完美匹配问题
4.96/5 (20投票s)
本文旨在演示如何使用遗传算法解决一个 NP-Complete 问题，我以赛程生成问题为例。
目录
1. 引言
遗传算法在解决 NP-Complete 优化问题方面非常有用。这些问题通常有许多不同的参数可以同时变化，这使得遍历所有参数的所有组合在计算上非常缓慢且不可行。基本思想是从一个种群开始，让这个种群进化到一个更优良的状态。
2. 背景
所有术语和定义都在 维基百科 中有清晰的解释，我不会在此重新输入。在我的代码示例中，我使用了 GAF（遗传算法框架）这个框架，它由 **John Newcombe** 编写。感谢他，我无需处理遗传算法的实现细节，他已经完成了所有繁重的工作。他有一个很棒的关于这个的博客，我强烈建议你去看看。
通过 NuGet 将 GAF 添加到项目中；
PM> Install-Package GAF
以及来自该博客的一些话；
“遗传算法（GA）是软件开发人员最接近魔法的东西。看着一个问题的解决方案‘进化’，真是太棒了。”
有关 NP-Complete 问题的更多信息，请参阅 这里。
3. 遗传算法
3.1 工作原理
遗传算法类似于自然界中的过程；适者生存，或自然选择。这是一种计算的进化方法。在计算上，这个过程与生物过程非常相似。在运行遗传算法之前，必须采取两个关键步骤：
- 定义一组可能代表问题解决方案的个体。
- 定义一个可以量化个体接近良好答案程度的适应度函数。
让我们列出整个过程：
- 首先创建一个随机生成的初始种群。随机生成允许搜索空间中所有可能解的解候选（染色体）。
- 评估每个解候选，按适应度值降序排序，并取现有种群的一部分。适应度最高的个体将更频繁地进行交配，一部分适应度最低的个体将被丢弃。
- 使用这个集合来繁殖新一代并评估该集合。
- 用新产生的个体替换一部分死去的个体，并评估新个体。这样可以保持每一代种群的大小不变。
- 重复上一步，直到达到终止条件。
现在，简要谈谈遗传算子。
3.2 遗传算子
遗传算子就像我们在数学中使用的 + - / *。它们用于遗传算法中的生成和修剪操作。它们有我们需要根据问题进行设置的参数。
3.2.1 交叉
此算子用于将现有解决方案组合成其他解决方案，以此来维持 遗传多样性。在 GAF 中，交叉操作可以通过两种选项完成；单点交叉和双点交叉。它们在下面进行说明：
单点交叉
单点交叉操作接受两个染色体，随机选择一个索引，从染色体 1 取前一部分，从染色体 2 取后一部分，生成一个新的染色体。
双点交叉
在许多情况下，使用双点交叉更合适。它选择两个点并交换父母之间的中心部分。
这就是我们在 GAF 中定义交叉算子函数的方式：
(来自 John Newcombe 的博客)
var crossover = new Crossover(crossoverProbability, true)
{
CrossoverType = CrossoverType.SinglePoint
}; 交叉概率只是一个介于 0 和 1 之间的值，表示父母交叉产生后代的概率。值为 1 意味着所有选定的父母都会交叉并产生后代。值为 0.85 意味着 85% 的父母会交叉，其余父母将完好无损地传递到新一代。第二个参数与重复处理有关。
3.2.2 变异
变异算子作用于一个染色体。它简单地交换染色体中一些随机选择的基因的值。此算子也维持遗传多样性。
变异
这就是我们在 GAF 中定义变异算子函数的方式：
var mutate = new SwapMutate(mutationProbability); 3.2.3 精英
精英制允许最佳解决方案在不被修改的情况下传递到下一代。例如，对于 100 个个体的种群，5% 的精英意味着前 5 条染色体构成下一代的一部分。这意味着任何未来的世代至少和当前世代一样好。精英制有助于保护优良的个体。然而，研究表明，精英比例的增加会导致种群内重复个体的数量增加，从而降低 GA 的性能。
这就是我们在 GAF 中定义精英算子函数的方式：
var elite = new Elite(elitismPercentage); 4. 完美匹配问题
给定一个图 G = (V,E)，图 G 中的匹配 M 是一个无向边集；也就是说，没有两条边共享同一个顶点。完美匹配是匹配了图中所有顶点的匹配。也就是说，图中的每个顶点都恰好与匹配中的一条边相关联。完美匹配也是一个最小尺寸的 边覆盖（来自 维基百科）。要解决这个问题，顶点数必须是 **偶数**。
在上图中，只有 (b) 部分显示了完美匹配。现在假设边的长度不相等，我们正在尝试找到导致边长度总和最短的最佳完美匹配。此时，问题变得更加复杂。如果我们有一个具有 A、B、C、D 顶点的四边形，所有可能的解决方案是：
- A-B , C-D => 7 + 4 = 11
- A-C, B-D => 5 + 3 = 8
- A-D, B-C => 6 + 11 = 17
第二个解决方案成本为 8，是最佳匹配。对于四边形来说很简单，如果是六边形呢？
15 种可能的解决方案。定义所有这些并计算总权重现在看起来更难了。如果我们有 8 个顶点，解决方案的数量将是 105，然后是 945、10395、135135、2027025……复杂度增长更快。
其复杂度为 **n!!**，这被称为 双阶乘。
例如，9!! = 1 × 3 × 5 × 7 × 9 = 945。
5. 赛程生成问题
联赛赛程生成用于各种领域，我将讨论一个特定的领域，用于在 **桥牌** 比赛中匹配队伍的 **瑞士轮** 技术。我们需要为 n 支队伍生成 n-1 轮比赛，该问题的要求如下：
- 队伍数量应为偶数。
- 每对队伍只能匹配一次。
- 考虑匹配得分接近的队伍。
- 创建所有可能的轮次（如果队伍数量为 n，应创建 n-1 种可能的轮次）。
是的，这个问题与“完美匹配问题”完全相同，可以将每支队伍视为一个多边形的顶点。
我们将生成每轮可能的最佳匹配，使用遗传算法似乎非常适合这种情况。
6. 使用代码
我构建了一个 Model 来保存应用程序数据；它由 Player、Team、Match、Round 和 Session 类组成。
Player 类保存玩家 ID 和玩家姓名。
[Serializable]
public class Player
{
#region Fields
private string _id;
private string _name;
#endregion
#region ctor
public Player()
{
_id = Guid.NewGuid().ToString();
_name = "Player";
}
public Player(string name)
{
_id = Guid.NewGuid().ToString();
_name = name;
}
#endregion
#region Properties
[Browsable(false)]
public string Id
{
get { return _id; }
set { _id = value; }
}
public string Name
{
get { return _name; }
set { _name = value; }
}
#endregion
} Team 类保存队伍 ID、队伍名称、总得分、上轮排名、之前匹配的队伍和玩家列表。
[Serializable]
public class Team
{
#region Fields
private string _name;
private string _id;
private int _score;
private int rank;
private List<Team> _matchedTeams;
private Team _currentMatch;
private List<Player> _players;
#endregion
#region ctor
public Team()
{
_matchedTeams = new List<Team>();
_name = "Team";
_score = 0;
rank = 0;
_id = Guid.NewGuid().ToString();
}
public Team(string name = "Team", int score = 0)
{
_matchedTeams = new List<Team>();
_name = name;
_score = score;
_id = Guid.NewGuid().ToString();
}
#endregion
#region Properties
[Browsable(false)]
public string Id
{
get { return _id; }
set { _id = value; }
}
public string Name
{
get { return _name; }
set { _name = value; }
}
public int Score
{
get { return _score; }
set { _score = value; }
}
public List<Player> Players
{
get { return _players; }
set { _players = value; }
}
[Browsable(false)]
public Team CurrentMatch
{
get { return _currentMatch; }
set { _currentMatch = value; }
}
[Browsable(false)]
public List<Team> MatchedList
{
get { return _matchedTeams; }
set { _matchedTeams = value; }
}
public int Rank
{
get { return rank; }
set { rank = value; }
}
#endregion
#region Methods
public override string ToString()
{
return _name + " - (" + _score + ")";
}
public bool IsMatchedBefore(Team team)
{
return _matchedTeams.Contains(team);
}
#endregion
} Match 类保存一对匹配的队伍。
[Serializable]
public class Match
{
#region Fields
/// <summary>
/// Home team field of class
/// </summary>
private Team _homeTeam;
/// <summary>
/// Away team field of class
/// </summary>
private Team _awayTeam;
#endregion
#region ctor
/// <summary>
/// Initializes a new instance of the Match class, that matches two teams for a round
/// </summary>
/// <param name="home">Pass team for this parameter which holds for "Home Team"</param>
/// <param name="away">Pass team for this parameter which holds for "Away Team"</param>
public Match(Team home, Team away)
{
this._homeTeam = home;
this._awayTeam = away;
}
#endregion
#region Properties
/// <summary>
/// Gets or sets "Home Team" for current match object
/// </summary>
public Team HomeTeam
{
get { return this._homeTeam; }
set { this._homeTeam = value; }
}
/// <summary>
/// Gets or sets "Home Team" for current match object
/// </summary>
public Team AwayTeam
{
get { return this._awayTeam; }
set { this._awayTeam = value; }
}
#endregion
#region Methods
/// <summary>
/// Overrides ToString() method of class to visualize a better string representation
/// </summary>
/// <returns>Name of "Home Team" vs "Away Team"</returns>
public override string ToString()
{
if (_homeTeam == null || _awayTeam == null)
return "Empty Match!";
return _homeTeam.Name + " (" + _homeTeam.Score + ") vs " +
_awayTeam.Name + " (" + _awayTeam.Score + ")";
}
#endregion
} Round 类保存轮次 ID 和比赛列表，每轮比赛列表的数量将是队伍数量的一半。
[Serializable]
public class Round
{
#region Fields
private List<Match> _matches;
private int _id;
#endregion
#region ctor
public Round()
{
_matches = new List<Match>();
}
public Round(List<Match> matches)
{
_matches = matches;
}
#endregion
#region Properties
public List<Match> Matches
{
get { return _matches; }
set { _matches = value; }
}
public int Id
{
get { return _id; }
set { _id = value; }
}
#endregion
#region Methods
public List<Match> AddMatch(Match match)
{
_matches.Add(match);
return _matches;
}
public override string ToString()
{
if (_matches.Any())
{
return "Round: " + _id + Environment.NewLine + string.Join("\r\n", _matches) + "\r\n";
}
return "Round: No matches!";
}
#endregion
} Session 类保存轮次列表。
[Serializable]
public class Session
{
#region Fields
private List<Round> _rounds;
#endregion
#region ctor
public Session()
{
_rounds = new List<Round>();
}
#endregion
#region Properties
public List<Round> Rounds
{
get { return _rounds; }
set { _rounds = value; }
}
#endregion
#region Methods
public List<Round> AddRound(Round round)
{
_rounds.Add(round);
return _rounds;
}
public Round CreateARound(List<Match> matches)
{
if (matches != null && matches.Any())
{
var round = new Round(matches) {Id = Rounds.Count + 1};
_rounds.Add(round);
return round;
}
return null;
}
public override string ToString()
{
return "Round Count: " + _rounds.Count;
}
#endregion
} Model 保存队伍列表和比赛会话。
[Serializable]
public class Model
{
#region Fields
private List<Team> _teams;
private Session _mySession;
#endregion
#region ctor
public Model()
{
_teams = new List<Team>();
_mySession = new Session();
}
#endregion
#region Properties
public List<Team> Teams
{
get { return _teams; }
set { _teams = value; }
}
[Browsable(false)]
public Session MySession
{
get { return _mySession; }
set { _mySession = value; }
}
#endregion
#region Methods
public void AddRandomPointsToTeams()
{
_teams.ForEach(p => p.Score += Util.Util.RandomNumber(31));
}
public List<Team> AddTeam(Team team)
{
_teams.Add(team);
return _teams;
}
public List<Round> AddRound(Round round)
{
_mySession.AddRound(round);
return _mySession.Rounds;
}
public Round CreateARound(List<Match> matches)
{
return _mySession.CreateARound(matches);
}
public void ClearHistory()
{
_mySession.Rounds.Clear();
_teams.ForEach(p =>
{
p.Score = 0;
p.Rank = 0;
p.MatchedList.Clear();
p.CurrentMatch = null;
});
}
public bool IsGameEnd()
{
return (_mySession.Rounds.Count == _teams.Count - 1);
}
#endregion
} 现在我们准备进行计算了：
- 我将创建一个种群（我决定创建 100 个，但根据问题的大小，可能需要几百甚至几千个），
- 设置其染色体长度（在我们的问题中等于队伍数量）。
- 定义并添加遗传算子。
- 定义一个“适应度计算”方法，该方法以染色体为输入并返回一个 double 值。
- 将种群和适应度计算方法传递给遗传算法对象。
- 定义一个“
终止”方法，并通过将该方法作为委托传递来运行遗传算法。
生成计数是一个预设值，对于 20 支队伍，1000 代的生成计数效果很好。没有最佳的生成计数，GA 意味着“差不多就好”。你只需要决定什么算是足够好。
public List<Match> PickaMatchList()
{
var lastListMatch = new List<Match>();
double diffTotal = 0.0;
var population = new Population(_teams.Count);
for (var p = 0; p < 100; p++)
{
var chromosome = new Chromosome();
for (var g = 0; g < _teams.Count; g++)
{
chromosome.Genes.Add(new Gene(g));
}
//mix each chromosome up and add to the population
chromosome.Genes.Shuffle();
population.Solutions.Add(chromosome);
}
//create the elite operator
var elite = new Elite(5);
var crossover = new Crossover(1.0)
{
CrossoverType = CrossoverType.DoublePointOrdered
};
//create the SwapMutate operator
var mutate = new SwapMutate(0.2);
var ga = new GeneticAlgorithm(population, CalculateFitness);
//subscribe to the generation and run complete events
ga.OnGenerationComplete += (sender, e) =>
{
if (OnGenerationComplete != null)
OnGenerationComplete(sender, e);
};
ga.OnRunComplete += (sender, e) =>
{
var fittest = e.Population.GetTop(1)[0];
for (int i = 0; i < fittest.Genes.Count; i += 2)
{
lastListMatch.Add(new Match(_teams[(int)fittest.Genes[i].RealValue],
_teams[(int)fittest.Genes[i + 1].RealValue]));
}
diffTotal = CalculateDifference(fittest);
};
//add the operators
ga.Operators.Add(elite);
ga.Operators.Add(crossover);
ga.Operators.Add(mutate);
//run the GA
ga.Run(Terminate);
if (diffTotal >= _falseStateConstant)
return null;
lastListMatch.ForEach(p =>
{
p.HomeTeam.CurrentMatch = p.AwayTeam;
p.AwayTeam.CurrentMatch = p.HomeTeam;
p.AwayTeam.MatchedList.Add(p.HomeTeam);
p.HomeTeam.MatchedList.Add(p.AwayTeam);
});
return lastListMatch;
} 适应度函数的返回值需要介于 0 和 1 之间，数字越大表示适应度越高。
private double CalculateFitness(Chromosome chromosome)
{
var diffTotal = CalculateDifference(chromosome);
_generationCount = diffTotal == 0 ? 1 : _tempGenerationCount;
return 1 - diffTotal / (_falseStateConstant * _teams.Count);
} 关键在于如何实现适应度计算。
染色体为我们提供了一系列数组索引，我们需要将这些值映射到真实数据。然后按对分组元素并计算它们之间的排名差异。如果这对队伍之前已经匹配过，则添加一个较大的数字作为差异，这将导致一个较差的适应度值，并促使算法立即丢弃该染色体。
private double CalculateDifference(Chromosome chromosome)
{
var diffTotal = 0.0;
for (int i = 0; i < chromosome.Genes.Count; i += 2)
{
var teamHome = _teams[(int)chromosome.Genes[i].RealValue];
var teamAway = _teams[(int)chromosome.Genes[i + 1].RealValue];
if (!teamHome.IsMatchedBefore(teamAway))
{
var difference = Math.Abs(teamHome.Rank - teamAway.Rank);
diffTotal += difference;
}
else
{
diffTotal += _falseStateConstant;
}
}
return diffTotal;
}
private bool Terminate(Population population, int currentGeneration,long currentEvaluation)
{
return currentGeneration > _generationCount;
} 在每轮结束时，将新得分添加到队伍中，并在生成下一轮之前，通过此扩展方法重新计算排名：
public static void SortTeams(this List<Team> list)
{
list.Sort((a, b) => (b.Score.CompareTo(a.Score)));
for (int i = 0; i < list.Count; i++)
{
list[i].Rank = i;
}
} 
7. 结论
遗传算法（GA）是软件开发人员最接近魔法的东西。我生成了 40 支队伍的第 35 轮比赛，耗时不到 5 分钟。使用经典方法可能需要数月时间。GAF 为我打开了几扇门，它实现得非常好且可扩展，你甚至可以轻松创建自己的遗传算子。对我来说这是一次很好的经历，感谢阅读。
8. 历史
- 2014.05.25 - 初始版本