유전알고리즘 테스트

정비문제 테스트용


import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Random;


public class Main {


static int answerSize = 100; //해 사이즈

static int generationSize = 100;  //반복수행 세대수

static int chromosomeSize = 7; //염색체길이 (장비7개)


static int k = 3; //적합도 조정용 k


static double pc = 0.7; //교차율

static double pm = 0.01; //변이율

static Random random = new Random(System.currentTimeMillis());

static List<int[]> masterDataList = new ArrayList<int[]>();

static int[] capacity = {20,15,35,40,15,15,10}; //설비용량

static int[] demand = {80,90,65,70}; //기간별 수요


static int[] answerFitness = new int[answerSize]; //적합도 결과

static int[] adjustedFitness = new int[answerSize]; //적합도 조정값 결과

static HashMap<String, Integer> dataHistory = new HashMap<String, Integer>(); 

static int maxFitness = 0; //최적해 제시용 max수치

static int[] maxChromosome = new int[chromosomeSize]; //최적해용 데이터

static{

//기준 데이터 구성

int[] data1 = {12,6,3};

int[] data2 = {12,6,3};

int[] data3 = {8,4,2,1};

int[] data4 = {8,4,2,1};

int[] data5 = {8,4,2,1};

int[] data6 = {8,4,2,1};

int[] data7 = {8,4,2,1};


masterDataList.add(data1);

masterDataList.add(data2);

masterDataList.add(data3);

masterDataList.add(data4);

masterDataList.add(data5);

masterDataList.add(data6);

masterDataList.add(data7);

}

/**

* @param args

*/

public static void main(String[] args) {


List<int[]> answerList = new ArrayList<int[]>();

List<int[]> previousAnswerList = new ArrayList<int[]>();

//초기해 구성

int randomIndex = 0;

int[] dataArray = null;

for(int i=0; i < answerSize; i++){

int[] answerArray = new int[chromosomeSize];

for(int j=0; j < chromosomeSize; j++){

dataArray = masterDataList.get(j);

randomIndex = random.nextInt(dataArray.length); 

answerArray[j] = dataArray[randomIndex]; 

}

previousAnswerList.add(answerArray);

}


//적합도 계산

calculateFitnessAll(previousAnswerList);


for(int genCount=0; genCount < generationSize; genCount++ ){

//적합도 값 조정

calculateAdjustedFitness();

//교차할 염색체 선정

int sum = getSum(adjustedFitness);

int[] newAnswer = null;

for(int i=0; i < answerSize; i++ ){

//교체율 비교

if(random.nextDouble() > pc){

//변경하지 않고 그대로 사용

newAnswer = new int[chromosomeSize];

System.arraycopy(previousAnswerList.get(i), 0, newAnswer, 0, chromosomeSize);

}else{

//교차연산 수행

int selectedAnswer1 = selectNo(sum);

int selectedAnswer2 = selectNo(sum);

newAnswer = crossOver(previousAnswerList.get(selectedAnswer1), previousAnswerList.get(selectedAnswer2));

}


//변이율 기준으로 유전자 변경 (pm)

if(random.nextDouble() > pm){

int point = random.nextInt(chromosomeSize);

int[] masterData = masterDataList.get(point);

newAnswer[point] = masterData[random.nextInt(masterData.length)];

}

answerList.add(newAnswer);

}

previousAnswerList = answerList;

answerList = new ArrayList<int[]>();


//적합도 계산

calculateFitnessAll(previousAnswerList);

}

System.out.println("maximum=" + maxFitness);

for(int i=0; i < chromosomeSize; i++){

System.out.print(maxChromosome[i] + " ");

}


}


public static void calculateFitnessAll(List<int[]> list){

int fitness = 0;

for(int i=0; i < answerSize; i++){

fitness = calculateFitness(list.get(i));

answerFitness[i] = fitness;

}

//평균, min, max

float average = getSum(answerFitness) / answerSize;

int min = getMin(answerFitness);

int max = getMax(answerFitness);


System.out.println("average=" + average + ",max=" + max + ",min=" + min);


int maxIndex = dataHistory.get("max");

int[] chromosome = list.get(maxIndex);

for(int i=0; i < chromosomeSize; i++){

System.out.print(chromosome[i] + " ");

}

System.out.print("\n");


if(max > maxFitness){

maxFitness = max;

maxChromosome = new int[chromosomeSize];

System.arraycopy(chromosome, 0, maxChromosome, 0, chromosomeSize);

}


}

public static int[] crossOver(int[] answer1, int[] answer2){

int cutPoint = random.nextInt(chromosomeSize);

int[] newAnswer = new int[chromosomeSize];

System.arraycopy(answer1, 0, newAnswer, 0, cutPoint);

System.arraycopy(answer2, cutPoint, newAnswer, cutPoint, chromosomeSize-cutPoint);

return newAnswer;

}

public static void calculateAdjustedFitness(){

//fitness 조정 

int[] answer = null;

int minA = getMin(answerFitness);

int maxA = getMax(answerFitness);

int base = maxA - minA;

for(int i=0, size=answerFitness.length; i < size; i++){

adjustedFitness[i] = base + (answerFitness[i] - minA)/(k-1);

}

}

public static int selectNo(int adjustedFitnessSum){

double sum = 0;

int selectedNo = 0;

if(adjustedFitnessSum <= 0){

selectedNo = random.nextInt(answerSize);

}else{

int point = random.nextInt(adjustedFitnessSum);

for(int i=0; i < answerSize; i++){

sum += answerFitness[i];

if(point <= sum){

selectedNo = i;

break;

}

}

}

return selectedNo;

}


public static int calculateFitness(int[] answerArray){

int[] result = {150,150,150,150};

//각 기간별로 체크

for(int i=0; i < answerArray.length; i++){

//기간1

if((answerArray[i] & 8) > 0){

result[0] -= capacity[i];

}

//기간 2

if((answerArray[i] & 4) > 0){

result[1] -= capacity[i];

}

//기간 3

if((answerArray[i] & 2) > 0){

result[2] -= capacity[i];

}

//기간 4

if((answerArray[i] & 1) > 0){

result[3] -= capacity[i];

}

}


int min = Integer.MAX_VALUE;

for(int i=0; i < demand.length; i++){

result[i] -= demand[i];

if(result[i] < min){

min = result[i];

}

}

return min;

}

public static int getMin(int[] data){

int min = Integer.MAX_VALUE;

for(int i=0, size=data.length; i < size; i++){

if(data[i] < min ){

min = data[i];

}

}

return min;

}

public static int getMax(int[] data){


int max = Integer.MIN_VALUE;

for(int i=0, size=data.length; i < size; i++){

if(data[i] > max ){

max = data[i];

dataHistory.put("max", i);

}

}

return max;

}

public static int getSum(int[] data){

int sum = 0;

for(int i=0, size=data.length; i < size; i++){

sum += data[i];

}

return sum;

}

}