遗传算法优化
遗传算法的效率和求解质量很大程度上取决于其算子设计和参数调整。本章深入探讨如何优化遗传算法，特别是针对TSP等复杂组合优化问题，通过精心设计的算子和处理技术来提高算法性能。
5.1 TSP用的各种算子
TSP（旅行商问题）作为一个典型的NP-Hard问题，对遗传算法的各种组件都提出了挑战。针对TSP问题的特殊性，我们需要设计特定的算子以保证解的有效性和收敛效率。
5.1.1 各种置换变异算子
变异算子是保持种群多样性和探索能力的关键。针对TSP问题的置换编码，我们需要特殊的变异方法以确保产生的路径仍然是有效的（每个城市恰好访问一次）。
1. 交换变异(Swap Mutation)
最基本的置换变异方法，随机选择路径中的两个城市并交换它们的位置。
csharp
/// <summary>
/// 交换变异算子
/// </summary>
public static void SwapMutation(int[] path)
{
int length = path.Length;
// 随机选择两个不同的位置
int pos1 = Random.Range(0, length);
int pos2;
do {
pos2 = Random.Range(0, length);
} while (pos2 == pos1);
// 交换这两个位置的城市
int temp = path[pos1];
path[pos1] = path[pos2];
path[pos2] = temp;
}
// 使用示例
void ApplyMutation(int[] path)
{
Debug.Log("应用交换变异前的路径: " + string.Join("-", path));
SwapMutation(path);
Debug.Log("应用交换变异后的路径: " + string.Join("-", path));
// 验证解的有效性
bool isValid = ValidatePath(path);
Debug.Log("路径有效性: " + isValid);
}
// 验证路径有效性（每个城市恰好出现一次）
bool ValidatePath(int[] path)
{
HashSet<int> cities = new HashSet<int>();
foreach (int city in path)
{
if (cities.Contains(city))
return false;
cities.Add(city);
}
return cities.Count == path.Length;
}
交换变异的优点是简单直观，缺点是每次只能小幅度改变解，可能需要多次变异才能产生显著不同的路径。
2. 插入变异(Insertion Mutation)
选择一个城市，将其从当前位置移除并插入到路径中的另一个位置。
csharp
/// <summary>
/// 插入变异算子
/// </summary>
public static void InsertionMutation(int[] path)
{
int length = path.Length;
// 随机选择一个城市和一个新位置
int sourcePos = Random.Range(0, length);
int targetPos = Random.Range(0, length);
// 如果源位置和目标位置相同，则不需要变异
if (sourcePos == targetPos)
return;
// 保存要移动的城市
int cityToMove = path[sourcePos];
// 将城市从源位置移除并插入到目标位置
if (sourcePos < targetPos)
{
// 向左移动元素
for (int i = sourcePos; i < targetPos; i++)
{
path[i] = path[i + 1];
}
}
else
{
// 向右移动元素
for (int i = sourcePos; i > targetPos; i--)
{
path[i] = path[i - 1];
}
}
// 将城市插入到目标位置
path[targetPos] = cityToMove;
}
// 使用示例
void DemonstrateInsertionMutation()
{
int[] path = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Debug.Log("原始路径: " + string.Join("-", path));
InsertionMutation(path);
Debug.Log("插入变异后: " + string.Join("-", path));
}
插入变异可以产生比交换变异更大的变化，对于路径优化特别有效，因为它保留了部分城市的相对顺序。
3. 倒序变异(Inversion Mutation)
选择路径中的一个子序列，将其顺序颠倒。这对TSP特别有效，因为它可以消除路径中的交叉。
csharp
/// <summary>
/// 倒序变异算子
/// </summary>
public static void InversionMutation(int[] path)
{
int length = path.Length;
// 随机选择两个位置，确定一个子序列
int pos1 = Random.Range(0, length);
int pos2 = Random.Range(0, length);
// 确保pos1 <= pos2
if (pos1 > pos2)
{
int temp = pos1;
pos1 = pos2;
pos2 = temp;
}
// 反转子序列
while (pos1 < pos2)
{
int temp = path[pos1];
path[pos1] = path[pos2];
path[pos2] = temp;
pos1++;
pos2--;
}
}
// 使用示例，比较在TSP中的效果
void CompareMutationEffects()
{
// 创建TSP问题实例
TSPProblem tspProblem = CreateSampleTSPProblem(10);
// 创建一个初始路径
int[] originalPath = Enumerable.Range(0, 10).ToArray();
ShuffleArray(originalPath);
// 复制路径进行不同变异
int[] swapPath = (int[])originalPath.Clone();
int[] insertionPath = (int[])originalPath.Clone();
int[] inversionPath = (int[])originalPath.Clone();
// 应用不同变异
SwapMutation(swapPath);
InsertionMutation(insertionPath);
InversionMutation(inversionPath);
// 计算并比较路径长度
float originalDistance = tspProblem.CalculatePathDistance(originalPath);
float swapDistance = tspProblem.CalculatePathDistance(swapPath);
float insertionDistance = tspProblem.CalculatePathDistance(insertionPath);
float inversionDistance = tspProblem.CalculatePathDistance(inversionPath);
Debug.Log($"原始路径长度: {originalDistance}");
Debug.Log($"交换变异后长度: {swapDistance}");
Debug.Log($"插入变异后长度: {insertionDistance}");
Debug.Log($"倒序变异后长度: {inversionDistance}");
}
倒序变异特别适合TSP问题，因为它可以修复路径中的交叉点，这些交叉通常会导致路径长度增加。
4. 移位变异(Displacement Mutation)
选择一个子序列，将其整体移动到路径中的另一个位置。这结合了插入变异和倒序变异的特点。
csharp
/// <summary>
/// 移位变异算子
/// </summary>
public static void DisplacementMutation(int[] path)
{
int length = path.Length;
// 需要至少4个城市才能进行有意义的移位变异
if (length < 4)
return;
// 随机选择子序列的长度(1到length/2)
int subseqLength = Random.Range(1, length / 2 + 1);
// 随机选择子序列的起始位置
int startPos = Random.Range(0, length - subseqLength);
// 随机选择插入位置(不在子序列范围内)
int insertPos;
do {
insertPos = Random.Range(0, length - subseqLength + 1);
} while (insertPos > startPos - subseqLength && insertPos <= startPos);
// 创建临时数组保存子序列
int[] subsequence = new int[subseqLength];
for (int i = 0; i < subseqLength; i++)
{
subsequence[i] = path[startPos + i];
}
// 创建一个新的路径数组
int[] newPath = new int[length];
int newIndex = 0;
// 复制子序列前的部分
for (int i = 0; i < startPos; i++)
{
newPath[newIndex++] = path[i];
}
// 跳过子序列
for (int i = startPos + subseqLength; i < length; i++)
{
newPath[newIndex++] = path[i];
}
// 插入子序列到新位置
int[] finalPath = new int[length];
newIndex = 0;
for (int i = 0; i < insertPos; i++)
{
finalPath[newIndex++] = newPath[i];
}
for (int i = 0; i < subseqLength; i++)
{
finalPath[newIndex++] = subsequence[i];
}
for (int i = insertPos; i < length - subseqLength; i++)
{
finalPath[newIndex++] = newPath[i];
}
// 将结果复制回原数组
for (int i = 0; i < length; i++)
{
path[i] = finalPath[i];
}
}
// 使用示例
void TestDisplacementMutation()
{
int[] path = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Debug.Log("原始路径: " + string.Join("-", path));
DisplacementMutation(path);
Debug.Log("移位变异后: " + string.Join("-", path));
}
移位变异能够保留子序列内部的相对顺序，同时对整体路径进行较大调整，对破解局部最优解特别有效。
5. 自适应变异率
变异率是遗传算法的关键参数，过高会破坏良好解，过低会导致早熟收敛。自适应变异率策略可以根据进化过程动态调整变异率。
csharp
/// <summary>
/// 自适应变异控制器
/// </summary>
public class AdaptiveMutationController
{
// 变异率范围
private float minMutationRate;
private float maxMutationRate;
// 种群统计
private float bestFitness;
private float avgFitness;
private float prevAvgFitness;
// 当前变异率
private float currentMutationRate;
// 代数计数
private int generation;
private int stagnationCounter;
public AdaptiveMutationController(float minRate = 0.01f, float maxRate = 0.1f)
{
minMutationRate = minRate;
maxMutationRate = maxRate;
currentMutationRate = (minRate + maxRate) / 2;
generation = 0;
stagnationCounter = 0;
}
/// <summary>
/// 更新种群统计信息
/// </summary>
public void UpdateStatistics(float best, float average)
{
prevAvgFitness = avgFitness;
bestFitness = best;
avgFitness = average;
generation++;
// 检测停滞
if (generation > 1)
{
float improvementRate = (avgFitness - prevAvgFitness) / prevAvgFitness;
if (improvementRate < 0.01f) // 很小的改进
{
stagnationCounter++;
}
else
{
stagnationCounter = 0;
}
}
// 更新变异率
UpdateMutationRate();
}
/// <summary>
/// 根据进化状态更新变异率
/// </summary>
private void UpdateMutationRate()
{
// 如果种群多样性下降（最佳适应度远高于平均适应度）
float diversityRatio = avgFitness / (bestFitness + float.Epsilon);
// 根据多样性和停滞状态调整变异率
if (stagnationCounter > 5)
{
// 长时间停滞，增加变异率促进探索
currentMutationRate = Mathf.Min(maxMutationRate, currentMutationRate * 1.5f);
}
else if (diversityRatio < 0.6f)
{
// 多样性低，略微增加变异率
currentMutationRate = Mathf.Min(maxMutationRate, currentMutationRate * 1.1f);
}
else
{
// 正常收敛，逐渐减小变异率
currentMutationRate = Mathf.Max(minMutationRate, currentMutationRate * 0.95f);
}
}
/// <summary>
/// 获取当前变异率
/// </summary>
public float GetMutationRate()
{
return currentMutationRate;
}
/// <summary>
/// 根据个体适应度获取个性化变异率
/// </summary>
public float GetIndividualMutationRate(float individualFitness)
{
// 适应度高的个体使用较低变异率，适应度低的个体使用较高变异率
float fitnessFactor = individualFitness / (bestFitness + float.Epsilon);
fitnessFactor = Mathf.Clamp01(fitnessFactor);
return currentMutationRate * (1.0f - 0.5f * fitnessFactor);
}
}
// 在遗传算法中使用自适应变异控制器
void UseAdaptiveMutation(List<int[]> population, TSPProblem problem)
{
// 创建自适应变异控制器
AdaptiveMutationController mutationController = new AdaptiveMutationController(0.01f, 0.2f);
for (int generation = 0; generation < 1000; generation++)
{
// 评估种群
List<float> fitnessValues = new List<float>();
float bestFitness = float.MinValue;
foreach (var individual in population)
{
float fitness = 1.0f / problem.CalculatePathDistance(individual);
fitnessValues.Add(fitness);
if (fitness > bestFitness)
bestFitness = fitness;
}
float avgFitness = fitnessValues.Average();
// 更新变异控制器
mutationController.UpdateStatistics(bestFitness, avgFitness);
// 创建新一代
List<int[]> newPopulation = new List<int[]>();
// 选择和交叉操作...
// 使用自适应变异
for (int i = 0; i < population.Count; i++)
{
int[] individual = population[i];
float individualFitness = fitnessValues[i];
// 获取个性化变异率
float mutationRate = mutationController.GetIndividualMutationRate(individualFitness);
// 根据个性化变异率决定是否变异
if (Random.value < mutationRate)
{
// 随机选择变异类型
int mutationType = Random.Range(0, 5);
switch (mutationType)
{
case 0:
SwapMutation(individual);
break;
case 1:
InsertionMutation(individual);
break;
case 2:
InversionMutation(individual);
break;
case 3:
DisplacementMutation(individual);
break;
case 4:
// 混合多种变异
if (Random.value < 0.5f)
SwapMutation(individual);
else
InversionMutation(individual);
break;
}
}
newPopulation.Add(individual);
}
// 更新种群
population = newPopulation;
}
}
自适应变异策略可以根据进化状态动态调整变异率，当种群多样性下降或进化停滞时增加变异率，促进探索；当找到良好解时降低变异率，保护良好解。
5.1.2 各种置换杂交算子
交叉算子允许合并两个父代的遗传信息以产生后代。针对TSP问题的置换编码，需要特殊的交叉算子以确保产生有效的路径。
1. 部分映射交叉(PMX)
PMX (Partially Mapped Crossover) 保持父代的绝对位置信息，通过映射关系解决冲突。
csharp
/// <summary>
/// 部分映射交叉(PMX)算子
/// </summary>
public static int[] PMXCrossover(int[] parent1, int[] parent2)
{
int length = parent1.Length;
int[] offspring = new int[length];
// 初始化子代为-1，表示未填充
for (int i = 0; i < length; i++)
{
offspring[i] = -1;
}
// 随机选择交叉区段
int crossPoint1 = Random.Range(0, length);
int crossPoint2 = Random.Range(0, length);
// 确保crossPoint1 <= crossPoint2
if (crossPoint1 > crossPoint2)
{
int temp = crossPoint1;
crossPoint1 = crossPoint2;
crossPoint2 = temp;
}
// 步骤1：将交叉区段从parent1复制到offspring
for (int i = crossPoint1; i <= crossPoint2; i++)
{
offspring[i] = parent1[i];
}
// 步骤2：标记已使用的城市
bool[] used = new bool[length];
for (int i = crossPoint1; i <= crossPoint2; i++)
{
used[parent1[i]] = true;
}
// 步骤3：创建映射关系处理冲突
Dictionary<int, int> mapping = new Dictionary<int, int>();
for (int i = crossPoint1; i <= crossPoint2; i++)
{
if (parent1[i] != parent2[i])
{
mapping[parent2[i]] = parent1[i];
}
}
// 步骤4：填充剩余位置
for (int i = 0; i < length; i++)
{
if (i < crossPoint1 || i > crossPoint2)
{
int valueToInsert = parent2[i];
// 如果该值已在子代中，使用映射关系寻找替代值
while (used[valueToInsert])
{
// 查找映射
if (mapping.ContainsKey(valueToInsert))
{
valueToInsert = mapping[valueToInsert];
}
else
{
// 这种情况应该不会发生，但为了健壮性保留
for (int j = 0; j < length; j++)
{
if (!used[j])
{
valueToInsert = j;
break;
}
}
}
}
offspring[i] = valueToInsert;
used[valueToInsert] = true;
}
}
return offspring;
}
// 使用示例
void DemonstratePMXCrossover()
{
int[] parent1 = { 8, 4, 7, 3, 6, 2, 5, 1, 9, 0 };
int[] parent2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Debug.Log("父代1: " + string.Join("-", parent1));
Debug.Log("父代2: " + string.Join("-", parent2));
int[] offspring = PMXCrossover(parent1, parent2);
Debug.Log("PMX后代: " + string.Join("-", offspring));
// 验证有效性
bool isValid = ValidatePath(offspring);
Debug.Log("路径有效性: " + isValid);
}
PMX的优点是能够保持父代中元素的绝对位置信息，适用于绝对位置信息很重要的问题。
2. 顺序交叉(OX)
OX (Order Crossover) 保持父代的相对顺序信息，对TSP问题特别有效。
csharp
/// <summary>
/// 顺序交叉(OX)算子
/// </summary>
public static i
最低0.47元/天 解锁文章
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
