Kl算法及 1-優化 2-式劃分java實作

• Kl算法
• λ-優化與 2 式劃分
• JAVA實作

Kl算法

KL 算法是 Kernighan 與 Lin 兩個人在 1970 年設計一個圖劃分算法，是在尋找圖 G 的一個極小成本的可許劃分。KL 算法也是一種基于貪心算法的劃分算法，通過交換兩子產品中的元素實作兩子產品間通信代價極小化。由于貪心算法會導緻局部最優解，KL 算法在交換子產品中元素時把所有可能交換後産生的代價增益都計算出來，從中選擇一個最好的交換元素進行交換。這樣在某種程度上降低了局部最優的風險，但會造成算法的時間複雜性。不過，KL 算法在很大程度上會給出全局最優解。實驗表明 KL 算法給出的劃分通信代價極小化是最好的。

【異構分布式嵌入式系統的優化設計方法，許巾一，陳儀香，李凱旋，2020 年 1 月】

λ-優化與 2 式劃分

λ 優化：兩個集合間的λ點互換是指交換這兩個集合的λ元素。1-互換是将一個集合的單點與另一個集合的單點進行互換。一個配置稱為 1-優化，若不再存在 1-互換導緻劃分成本的下降。

2 式劃分：最簡單劃分問題是：給一個 2n 節點的圖 G，其中每

個節點都擁有相同的尺寸，尋找一個極小成本劃分将 2n 節點劃分成都含有 n

個節點的兩個集合。

算法具體詳細邏輯可參考文章連結: Kernighan-Lin算法.

JAVA實作

import java.util.Arrays;

public class Kl
{

	public static void main(String[] args)
	{
		double[][] matr=
	    	{
	    	    {0, 0, 0.5, 0, 0.5, 0, 0, 0},
	    	    {0, 0, 0.5, 0.5, 0, 0, 0, 0},
	    	    {0.5, 0.5, 0, 0.5, 1, 0.5, 0, 0},
	    	    {0, 0.5, 0.5, 0, 0, 1, 0, 0},
	    	    {0.5, 0, 1, 0, 0, 0.5, 1, 0},
	    	    {0, 0, 0.5, 1, 0.5, 0, 0.5, 0.5},
	    	    {0, 0, 0, 0, 1, 0.5, 0, 0.5},
	    	    {0, 0, 0, 0, 0, 0.5, 0.5, 0},};//導入通信代價矩陣
		char[] charA= {'a','c','d','f'};//初始化分組1
		char[] charB= {'b','e','g','h'};//初始化分組2
		
		System.out.print("初始2-劃分集為:\n{");
		for(char i:charA)
			System.out.print(i+",");
		System.out.print("}\n{");
		for(char i:charB)
			System.out.print(i+",");
		System.out.println("}");
		
		int[] A= new int[charA.length];
		int[] B= new int[charB.length];
		
		for(int i=0;i<charA.length;i++)
		{
			A[i]=charA[i]-'a';
			B[i]=charB[i]-'a';
		}
		
		double Gain=1;
		Kl kl=new Kl();
		while(Gain>0)
		{
			int[] tempA=Arrays.copyOf(A, A.length);
			int[] tempB=Arrays.copyOf(B, B.length);
			
			int[][] change=new int[2][A.length];//同一列元素分别表示替換元素組
			double[] maxg=new double[A.length];
			
			while(tempA.length!=0)
			{

				double[][] G=kl.countG(matr,tempA,tempB);
				
				
				for(int i=0;i<tempA.length;i++)//最大g值，以及對應元素組
				{
					for(int j=0;j<tempB.length;j++)
					{
						if(i==0&&j==0)
							{
								maxg[A.length-tempA.length]=G[i][j];
								change[0][A.length-tempA.length]=tempA[0];
								change[1][B.length-tempB.length]=tempB[0];
							}
						else
						{
							if(G[i][j]>maxg[A.length-tempA.length])
							{
								maxg[A.length-tempA.length]=G[i][j];
								change[0][A.length-tempA.length]=tempA[i];
								change[1][B.length-tempB.length]=tempB[j];
							}
						}
					}
				}
				//删除對應集合内最大收益元素
				tempA=kl.arrayReduce(tempA, change[0][A.length-tempA.length]);
				tempB=kl.arrayReduce(tempB, change[1][B.length-tempB.length]);

			}
			//求最大收益Gain需要換的元素個數
			double sumMax[]=new double[maxg.length];
			System.out.println("maxg\t\tchangA\t\tchangeB");
			for(int i=0;i<maxg.length;i++)
			{
				System.out.println(maxg[i]+"\t\t"+change[0][i]+"\t\t"+change[1][i]);
				for(int j=0;j<=i;j++)
				{
					sumMax[i]+=maxg[j];
				}
			}
			int count=0;
			for(int i=0;i<sumMax.length;i++)
			{
				if(i==0)
					Gain=sumMax[i];
				else
					if(sumMax[i]>Gain)
					{
						Gain=sumMax[i];
						count=i;
					}
			}
			System.out.println("max Gain="+Gain);

			//将A,B數組内收益最大化元素互換
			if(Gain<=0)
			{
				break;
			}
			else
			{
				for(int i=0;i<=count;i++)
				{
					for(int j=0;j<A.length;j++)
						if(A[j]==change[0][i])
							A[j]=change[1][i];
					for(int j=0;j<A.length;j++)
						if(B[j]==change[1][i])
							B[j]=change[0][i];
				}
			}
		}
		
		System.out.println("1-優化，2式劃分簇分類如下：\n第一簇");
		for(int i:A)
			System.out.print((char)(i+'a')+",");
		System.out.println("\n第二簇");
		for(int i:B)
			System.out.print((char)(i+'a')+",");
		System.out.println("\n通信代價："+kl.calculateDistance(matr, A, B));

	}
	
	public double calculateDistance(double[][] matr,int[] A,int[] B)//計算簇間通信代價
	{
		double dis=0;
		for(int i=0;i<A.length;i++)
		{
			for(int j=0;j<A.length;j++)
			{
				dis+=matr[A[i]][B[j]];
			}
		}
		return dis;
	}
	
 	public int[] arrayReduce(int[] oldArray,int value)//從oldArray中去掉第已有的value既簇元素
	{
		int[] newArray=new int[oldArray.length-1];
		for(int i=0,j=0;i<oldArray.length;i++)
		{
			if(oldArray[i]!=value)
			{
				newArray[j++]=oldArray[i];
			}
		}
		return newArray;
	}
	
	public double[][] countG(double[][] matr,int[] A,int[] B)//計算收益
	{
		double[][] G=new double[A.length][B.length];
		double[][] D=countD(matr, A, B);
		System.out.println("G值表為：");
		for(int i=0;i<A.length;i++)
		{
			for(int j=0;j<B.length;j++)
			{
				G[i][j]=D[0][i]+D[1][j]-2*matr[A[i]][B[j]];
				System.out.print(G[i][j]+",");
			}
			System.out.println();
		}
		return G;
	}

	public double[][] countD(double[][] matr,int[] A,int[] B)//計算代價數組
	{
		double[][] D=new double[2][A.length];
		double[] EA=countE(matr, A, B);
		double[] EB=countE(matr, B, A);
		double[] IA=countI(matr, A);
		double[] IB=countI(matr, B);
		//System.out.println("DA,DB\t\tEA,EB\t\tIA,IB");

		for(int i=0;i<A.length;i++)
		{
			D[0][i]=EA[i]-IA[i];
			D[1][i]=EB[i]-IB[i];
			//System.out.println(D[0][i]+","+D[1][i]+"\t\t"+EA[i]
			//		+","+EB[i]+"\t\t"+IA[i]+","+IB[i]);
		}
		System.out.println();
		return D;
	}
	
	public double[] countE(double[][] matr,int[] A,int[] B)//計算外代價
	{
		double[] E=new double[A.length];
		for(int i=0;i<A.length;i++)
		{
			for(int j=0;j<B.length;j++)
			{
				E[i]+=matr[A[i]][B[j]];
			}
		}
		return E;
	}
	
	public double[] countI(double[][] matr,int[] A)//計算内代價
	{
		double[] I=new double[A.length];
		for(int i=0;i<A.length;i++)
		{
			for(int j=0;j<A.length;j++)
			{
				I[i]+=matr[A[i]][A[j]];
			}
		}
		return I;
	}
}