遗传算法-最大割（Max Cut）问题及算法实现

有权重的无向图最大割

如图所示,现有无向图G=(V,E)。
设U是V的一个子集。对任意的顶点u,v: 如果(u,v)这条边属于E的一条边,此时u在U中，那么v一定不在U中，这样的边就称为顶点集合U的一个割边,所有的割边集合将集合V分成了两个顶点子集合。顶点集合U对应的所有的割边就构成图G的一个割。
最大割就是指含割边最多的割。

下图为这个无向图G的一个最大割,u集合为{1,6,8,9},v集合为{2,3,4,5,7,10},cut为8：

编程要求及思路

数据输入

第一行2个整数 n,e表示顶点个数和边个数。
第二行开始对应的数据分别为: 点1 点2 边（顶点编号从1-n）

上图G所对应的输入文件: simple.txt

10 14
1 8 1
2 4 1 
2 6 1
2 9 1 
2 10 -1
4 8 1
4 10 -1
5 8 1
5 9 1
5 10 -1
6 9 1
6 10 1
9 7 1
10 1 1

数据输出

第一行是最大割的边数。
第二行是顶点集的向量对应1-n,0表示不在集合，1表示在集合。

vertex number：10
edge number：14
each edge：
1 8 1
2 4 1
2 6 1
2 9 1
2 10 -1
4 8 1
4 10 -1
5 8 1
5 9 1
5 10 -1
6 9 1
6 10 1
9 7 1
10 1 1
maxcut is: 8
1 0 1 1 1 1 1 0 0 0

解题思想 (BFS)

这道题也是一个子集选取问题，所以它的解空间树是一个子集树。
**这个集合n个元素，每个元素可以有选取或不选取2种选择，所以共用2^n个子集。**这里用分支界限法。

分支界限法：类似宽度优先搜索，它每次都取一个节点，然后把它的所有的子节点都扩展，然后加到队列中，所以说，分支界限法，这种扩展方式导致每个节点每次最多一次扩展机会，它在扩展它的分支的时候，根据一定的界限条件，或淘汰不可能产生最优解的分支。

在这里我们用优先级队列(priority queue) + 分支界限法进行编程：

1. 建立一个HeapNode的结构体，重载operator < 让节点在优先队列中按照cut值从大到小排序。
2. 建立头结点，初始头结点的深度depth = 0, cut = 0, edges = e;
3. 初始继承头结点，将depth = 0的结点放入割集，将所有与其构成边的权重加入cut。将其压入优先级队列。
4. 将满足界限条件的E也压入优先级队列。
5. 从优先级队列中取出top结点设为E,从depth+1开始重复上述过程。
6. 直到depth == 点数，将最优割和割集放入bestcut中。（queue中所有的node都会测试到depth == 点数为止）

代码实现（BFS）

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int n,e,w=0;                    //顶点数和边数,总权重
int Graph[200][200];          //存储图的邻接矩阵
int bestcut = 0;              //存储最优解
int bestx[200];               //存储最优解
struct HeapNode               //队列节点
{
    int dep;
    int cut;
    int edges;
    int x[200];
    
    HeapNode()
    {
        memset(x,0,sizeof(x));
    }
        
    bool operator < (const HeapNode&a)const
    {
        return cut<a.cut;    //从大到小排序
    }
};

void maxcut()
{
    HeapNode E;             //根节点
    priority_queue<HeapNode> Q;
    E.cut = 0;
    E.edges = w;
    E.i = 0;
    
    while (1)
    {
        if (E.dep == n)
        {
            if (E.cut > bestcut)
            {
                bestcut = E.cut;
                memcpy(bestx, E.x, sizeof(int)*n);
            }
        }
        else
        {
            HeapNode temp = E;
            int depth = E.dep;
           
            for (int j = 0; j < n; j++)
            {
                if (Graph[depth][j])
                {
                    if (temp.x[j])
                    {
                        temp.cut -= Graph[depth][j];
                    }
                    else
                    {
                        temp.cut += Graph[depth][j];
                        temp.edges -= Graph[depth][j];
                    }
                }

            }
                        
            temp.x[depth] =1;
            temp.dep++;
            Q.push(temp);
                        
            if(E.cut + E.edges > bestcut) //界限条件(在E的前提下，如果加上剩余的edge权重能好过bestcut，则深度加一并且push到优先队列中)
            {
                E.dep++;
                Q.push(E);
            }
        }
        if(Q.size()==0) //队列为空跳出循环
        {
            break;
        }
        
        E = Q.top();    //选取cut最大的node操作
        Q.pop();
    }
}


int main()
{
	ifstream fin("simple.txt");   //输入文件
    cout << "vertex number：";
    fin >> n; cout << n;
    cout << "\nedge number：";
    fin  >> e; cout << e;
    cout << "\neach edge：\n";

    int a, b, c, i;
    for(i=0; i<e; i++)
    {
        fin >> a >> b >> c;
        w += c;
        Graph[a-1][b-1] = Graph[b-1][a-1] = c;  //将线段权重存储在邻接矩阵中
        cout << a << " " << b << " " << c << endl;
    }

    maxcut();
    cout << "maxcut is: " << bestcut << endl;         //输出最大割
    
    for (int k = 0; k < n; k++)        
    {
        cout << bestx[k] << " ";
    }
    cout << endl;
    return 0;
}

解题思想 (Genetic Algorithm)

遗传算法理论：

遗传算法（英语：genetic algorithm (GA) ）是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等等。

遗传算法模拟了达尔文的自然选择，这意味着一个人口要想生存就必须不断地自我完善。 最好的个体应该通过其健身价值来激发后代。。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

遗传算法步骤：

1）产生初始种群
2）获取第一人口的健身价值并记录最佳个体
3）通过适应性选择父母，并从选定的父母中抚养孩子，变异新一代的基因（基因的交叉和变异）
4）更新新人群的适应度并记录最佳个人
5）新一代换代（基因的交叉和变异）

遗传算法的结构：

1）基因型结构：int cut, float fitness（适应度）, int gene[1000]
2）染色体设计：设置整数类型顶点数数组，0表示不属于集合S，1表示属于集合S。
3）选择：使用适应度值随机生成父索引
4）交叉：从0到顶点之间随机选择一个数字，将父母基因以此索引为基准分开，然后将父母基因重组成为子代基因。
5）突变：使用突变率改变基因，如果基因为1，则将其更改为0，如果基因为0，则将其更改为1。

代码实现（Genetic Algorithm）

#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <string>
#include <string.h>
using namespace std;

#define VertexMaxSize 1000
#define EdgeMaxSize 10000
#define PopulationSize 120  // Number of population
#define CrossoverRate 0.9   // Probablity of crossover
#define MutateRate 0.2     // Probablity of mutation
#define ReplaceRate 0.5     // Probablity of replacement

int vertex, edges;      // vertex, edge
int bestcut = 0;       // store the best cut value of population
int worstcut = 0;      // store the worst cut value of population  
float allFit = 0;
int limitCut;
int timeStamp = 5;
string filename = "maxcut.in";     //input file's name
struct Edge
{
	int startIndex;
	int endIndex;
	int weight;
};

struct Genotype
{
	int cut;           // Cut value
	float fitness;     // Fi = (Cw-Ci) + (Cw-Cb)/(k-1)
	int gene[VertexMaxSize];     // store points which belongs to S set

	Genotype()
	{
		memset(gene, 0, sizeof(gene));
	}
	
	void printGene()
	{
        ofstream SaveFile("maxcut.out");
		for (int i = 0; i < vertex; i++)
		{
            if (gene[i] == 1)
                SaveFile << i+1 << " ";
		}
        SaveFile << endl;
        SaveFile.close();
	}
};
Genotype best;

struct Genotype population[PopulationSize + 1];
struct Genotype newpopulation[PopulationSize + 1];
struct Edge edgelist[EdgeMaxSize + 1];

void randomSet(int index);
void initial(string filename);
int calCut(Genotype GT);
float calFit(Genotype GT);
void crossover(Genotype *P1, Genotype *P2, Genotype *C1, Genotype *C2);
int selectIndex(Genotype Pop[PopulationSize + 1]);
void mutation(int index, float mRate);
void replace();
void localSearch(int range);
void maxcut();
void UpdateGroupValue();


void randomSet(int index)
{
	int num = rand() % 3;
	population[index].gene[0] = 1;

	if (num == 0)
	{
		for (int j = 1; j < vertex; j++)
		{
			int temp = rand() % 10;
			if (temp < 3)
			{
				population[index].gene[j] = 1;     // generate random number
			}
			else
			{
				population[index].gene[j] = 0;     // generate random number
			}
		}
	}

	if (num == 1)
	{
		for (int j = 1; j < vertex; j++)
		{
			int temp = rand() % 10;
			if (temp < 5)
			{
				population[index].gene[j] = 1;     // generate random number
			}
			else
			{
				population[index].gene[j] = 0;     // generate random number
			}
		}
	}

	if (num == 2)
	{
		for (int j = 1; j < vertex; j++)
		{
			int temp = rand() % 10;
			if (temp < 7)
			{
				population[index].gene[j] = 1;     // generate random number
			}
			else
			{
				population[index].gene[j] = 0;     // generate random number
			}
		}
	}
	
	population[index].cut = calCut(population[index]);
}

//    Initialize the vertex number, edge number through input file.
//    Store every edge into the edgelist
//    Random generate PopulationSize Genotype's gene array
//    Calculate each Genotype's cut
//    Record the best cut and worst cut
//    Calculate each Genotype's fitness value
void initial(string filename)
{
	int temp1, temp2, temp3;
	ifstream input;
	input.open(filename.c_str());
	srand((unsigned)time(NULL));

	if (!input)     // File check
	{
		cout << "Can not read input file, please check the input filename again\n";
		exit(1);
	}

	input >> vertex >> edges;
	cout << "vertex is :" << vertex << endl;
	cout << "edge is :" << edges << endl;

	if (vertex < 2)  //Vertex number check
		cout << "Can not crossover, please modify vertex number bigger than 2" << endl;

	//Store each edge's weight into edgelist
	for (int i = 0; i < edges; i++)
	{
		input >> temp1 >> temp2 >> temp3;
		edgelist[i].startIndex = temp1 - 1;
		edgelist[i].endIndex = temp2 - 1;
		edgelist[i].weight = temp3;
	}

	/*initialize each genotype's fitness and cut*/
	for (int i = 0; i < PopulationSize; i++)
	{
		randomSet(i);

		if (i == 0)
		{
			if (population[i].cut < 0)
				bestcut = 0;
			else
			{
				bestcut = population[i].cut;
				best = population[i];
			}
		}

		// Set best cut and worst cut in loop
		else
		{
			if (population[i].cut > bestcut)
			{
				bestcut = population[i].cut;
				best = population[i];
			}
			if (population[i].cut < worstcut)
				worstcut = population[i].cut;
		}
	//	localSearch(i);
	}

	UpdateGroupValue();

	cout << endl;
	cout << "Initial Generation: bestcut is: " << bestcut << endl;
}

void localSearch(int index)
{
	int cut;
	int array[VertexMaxSize];
	for (int i = 0; i < vertex; i++)
	{
		array[i] = i;
	}
	for (int i = 0; i < vertex/2; i++)
	{
		int temp1 = rand() % vertex;
		int temp2 = rand() % vertex;
		if (temp1 != temp2)
		{
			int temp = array[temp1];
			array[temp1] = array[temp2];
			array[temp2] = temp;
		}
	}

	for (int i = 0; i < vertex; i++)
	{
		population[index].gene[array[i]] = 1 - population[index].gene[array[i]];
		cut = calCut(population[index]);
		if (cut > population[index].cut)
		{
			if (cut > bestcut)
			{
				bestcut = cut;
				best = population[index];
				cout << "From local search: best cut is: " << bestcut << endl;
				best.printGene();
			}
			population[index].cut = cut;
		}
		else
		{
			population[index].gene[array[i]] = 1 - population[index].gene[array[i]];
		}
	}
}

int calCut(Genotype GT)
{
	int cutValue = 0, index1, index2;
	for (int i = 0; i < edges; i++)
	{
		index1 = edgelist[i].startIndex;
		index2 = edgelist[i].endIndex;
		if (GT.gene[index1] != GT.gene[index2])
		{
			cutValue += edgelist[i].weight;
		}
	}
	return cutValue;
}

float calFit(Genotype GT)
{
	float result;
	float fixedValue = 1.0 * (worstcut - bestcut) / (PopulationSize - 1);
	result = (worstcut - GT.cut) + fixedValue;
	return result;
}

void crossover(Genotype *P1, Genotype *P2, Genotype *C1, Genotype *C2)
{
	int sum = 0, temp;
	int num = rand() % vertex;

	for (int i = 0; i < num; i++)   // new child
	{
		C1->gene[i] = P1->gene[i];
		C2->gene[i] = P2->gene[i];
	}
	for (int i = num; i < vertex; i++)
	{
		C1->gene[i] = P2->gene[i];
		C2->gene[i] = P1->gene[i];
	}
	C1->cut = calCut(*C1);		 
	C2->cut = calCut(*C2);
}

int selectIndex(Genotype Pop[PopulationSize + 1])
{
	int sum = 0;
	int ranNum = -rand() % (int)(allFit);

	for (int i = 0; i < PopulationSize; i++)
	{
		if (sum < ranNum)
		{
			return i;
		}
		sum += Pop[i].fitness;
	}
	return PopulationSize - 1;
}

void UpdateGroupValue()
{
	allFit = 0;  //reset allfit
	for (int i = 0; i < PopulationSize; i++)
	{
		if (i == 0)
		{
			worstcut = population[i].cut;
		}
		else
		{
			if(population[i].cut < worstcut)
				worstcut = population[i].cut;
		}
		population[i].fitness = calFit(population[i]);
		allFit = allFit + population[i].fitness;
	}
}

void mutation(int index, float mRate)   //mutationRate = 1, delete bad mutation individual
{
	int num = mRate * 100;
	for (int k = 0; k < vertex; k++)
	{
		if (rand() % 100 < num)
		{
			population[index].gene[k] = 1 - population[index].gene[k];
			int cut = calCut(population[index]);
			if (bestcut < cut)
			{
				int dec = rand()%100;
				if(dec < 98)
				{
					bestcut = cut;
					best = population[index];
					population[index].cut = cut;
					cout << "From mutation: best cut is: " << bestcut << endl;
					best.printGene();
				}
				else{
					population[index].gene[k] = 1 - population[index].gene[k];
				}
			}
			else
			{
				if (population[index].cut < cut) {
					population[index].cut = cut;
				}
				else {
					population[index].gene[k] = 1 - population[index].gene[k];
				}
			}
		}
	}
}

void replace() 
{
	int choose = rand()%3;
	int cutList[PopulationSize];
	int limit;
	for (int i = 0; i < PopulationSize; i++)
	{
		cutList[i] = population[i].cut;
	}

	sort(cutList, cutList + PopulationSize);
	limit = (int)(PopulationSize * (ReplaceRate + 0.1 * choose));
	for (int i = 0; i < PopulationSize; i++)
	{
		if (population[i].cut < cutList[limit])
		{
			randomSet(i);
		}
	}
	
}

void maxcut()
{
	clock_t cstart, cend;
	int sIndex, eIndex;
	float sFit, eFit;
	cstart = clock();
	while (1)
	{
		cend = clock();
		 if (cend - cstart > 180 * CLOCKS_PER_SEC)    //end in 3 min
		 {
			 cout << "bestcut is "<<bestcut<<endl;
		    break;
		 }
		for (int i = 0; i < PopulationSize/2; i++)
		{
			sIndex = selectIndex(population);
			eIndex = selectIndex(population);
			memcpy(newpopulation, population, sizeof(Genotype)*(PopulationSize + 1));
	//		if (rand() % 10 < 8)  //crossoverRate = 0.8
			{
				// population crossover
				crossover(&population[sIndex], &population[eIndex], &newpopulation[sIndex], &newpopulation[eIndex]);
				if (newpopulation[sIndex].cut > population[sIndex].cut || newpopulation[sIndex].cut > population[eIndex].cut) 
				{
					if(population[sIndex].cut > population[eIndex].cut)
						memcpy(&population[eIndex], &newpopulation[sIndex], sizeof(Genotype));
					else
						memcpy(&population[sIndex], &newpopulation[sIndex], sizeof(Genotype));
				}
				if (newpopulation[eIndex].cut > population[sIndex].cut || newpopulation[eIndex].cut > population[eIndex].cut) 
				{
					if(population[sIndex].cut > population[eIndex].cut)
						memcpy(&population[eIndex], &newpopulation[eIndex], sizeof(Genotype));
					else
						memcpy(&population[sIndex], &newpopulation[eIndex], sizeof(Genotype));
				}
			}

			if (bestcut < newpopulation[sIndex].cut || bestcut < newpopulation[eIndex].cut) {
				if (newpopulation[eIndex].cut > newpopulation[sIndex].cut) {
					bestcut = newpopulation[eIndex].cut;
					best = newpopulation[eIndex];
				}
				else
				{
					bestcut = newpopulation[sIndex].cut;
					best = newpopulation[sIndex];
				}

				cout << "From crossover: best cut is: " << bestcut << endl;
			//	best.printGene();
			}		
		}
		for (int i = 0; i < PopulationSize; i++)
		{
			mutation(i, MutateRate);
		}
		int aa = (int)(cend - cstart);
		int now = aa/CLOCKS_PER_SEC;
		if (now >= timeStamp)    //end in 3 min
		{
			cout << "restart" << endl;
			replace();
			timeStamp = timeStamp + 3;
		}
		else
		{
			for (int i = 0; i < PopulationSize; i++)
			{
				localSearch(i);	
			}
		}
		UpdateGroupValue();
	}
	cout << "3 min finish" << endl;
}

int main()
{
	clock_t cstart, cend;
	initial(filename);
	maxcut();
	getchar();
	getchar();
	return 0;
}

Linux下运行C++程序

1. 新建一个文件夹,添加simple.txt和maxcut.cpp
2. 运行命令 g++ -o exe maxcut.cpp
3. 确认文件夹中生成exe文件后,运行命令 ./exe