ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 유전알고리즘 테스트
    최적화_통계_알고리즘/알고리즘 2013.02.18 01:27

    정비문제 테스트용


    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;

    }

    }

    댓글 0

Designed by Tistory.