AIM Lab Review

public void applyHeuristic(SAT problem) {
    // Select a random bit to flip
   int randomIndex = random.nextInt(problem.getNumberOfVariables());
   problem.bitFlip(randomIndex, CURRENT_SOLUTION_INDEX);
}

public void applyHeuristic(SAT problem) {
    double bestEval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);
    int bestIndex = 0;
    boolean improved = false;

    for (int j = 0; j < problem.getNumberOfVariables(); j++) {
        problem.bitFlip(j, CURRENT_SOLUTION_INDEX);
        double eval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);

        if (eval < bestEval) {
            bestIndex = j;
            bestEval = eval;
            improved = true;
        }
        problem.bitFlip(j, CURRENT_SOLUTION_INDEX);
    }

    if (improved) {
        problem.bitFlip(bestIndex, CURRENT_SOLUTION_INDEX);
    }
}

public void applyHeuristic(SAT problem) {
    double bestEval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);
    int[] perm = new int[problem.getNumberOfVariables()];

    for (int i = 0; i < problem.getNumberOfVariables(); i++) {
        perm[i] = i;
    }
    perm = ArrayMethods.shuffle(perm, random);

    for (int j = 0; j < problem.getNumberOfVariables(); j++) {
        problem.bitFlip(perm[j], CURRENT_SOLUTION_INDEX);
        double tempEval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);

        if (tempEval <= bestEval) {
            bestEval = tempEval;
        } else {
            problem.bitFlip( perm[j], CURRENT_SOLUTION_INDEX);
        }
    }
}

protected void runMainLoop() {
    for (int i = 0; i < iIntensityOfMutation; i++) {
        // apply mutation heuristic
       oMutationHeuristic.applyHeuristic(problem);
    }
    for (int i = 0; i < iDepthOfSearch; i++) {
        oLocalSearchHeuristic.applyHeuristic(problem);
    }
    double backEval = problem.getObjectiveFunctionValue(BACKUP_SOLUTION_INDEX);
    double newEval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);

    if (newEval <= backEval) {
        // accept new solution
       problem.copySolution(CURRENT_SOLUTION_INDEX, BACKUP_SOLUTION_INDEX);
    }else{
        // reject new solution
       problem.copySolution(BACKUP_SOLUTION_INDEX, CURRENT_SOLUTION_INDEX);
    }
}

protected void runMainLoop() {
    double temperature = oCoolingSchedule.getCurrentTemperature();
    double eval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);

    // Select a random bit to flip
   int randomIndex = random.nextInt(problem.getNumberOfVariables());
   problem.bitFlip(randomIndex, CURRENT_SOLUTION_INDEX);
   double newEval = problem.getObjectiveFunctionValue(CURRENT_SOLUTION_INDEX);
   double delta = newEval - eval;
   double probability = Math.exp(-delta/temperature);

   // If the new solution is better or the probability is higher, accept it
   if (delta < 0 || random.nextDouble() < probability) {
       problem.bitFlip(randomIndex, BACKUP_SOLUTION_INDEX);
   }else {
       problem.bitFlip(randomIndex, CURRENT_SOLUTION_INDEX);
   }

   // Update the temperature
   oCoolingSchedule.advanceTemperature();
}

public void advanceTemperature() {
    dCurrentTemperature *= this.dAlpha;
}

public void advanceTemperature() {
    dCurrentTemperature =  dCurrentTemperature / ( 1 + dBeta * dCurrentTemperature );
}

public void runMainLoop() {
    for(int iIterationCount = 0; iIterationCount < POPULATION_SIZE; iIterationCount += 2) {
        int iParent1, iParent2;
        iParent1 = p1Selection.parentSelection();
        iParent2 = p2Selection.parentSelection();
        if(iParent1 == iParent2) {
            iParent2 = (iParent1 + 1) % POPULATION_SIZE;
        }
        int iChild1 = POPULATION_SIZE + iIterationCount;
        int iChild2 = POPULATION_SIZE + iIterationCount +1;
        crossover.applyHeuristic(iParent1, iParent2, iChild1, iChild2);
        mutation.applyHeuristic(iChild1);
        localSearch.applyHeuristic(iChild1);
        mutation.applyHeuristic(iChild2);
        localSearch.applyHeuristic(iChild2);
    }
    // not forgetting to do replacement of the population AFTER all offspring are produced
   replacement.doReplacement(problem, POPULATION_SIZE);
}

public void applyHeuristic(int parent1Index, int parent2Index,
			int child1Index, int child2Index) {
    problem.copySolution(parent1Index, child1Index);
    problem.copySolution(parent2Index, child2Index);

    for(int i = 0; i < problem.getNumberOfVariables(); i++) {
        if(random.nextDouble() < 0.5) {
            problem.exchangeBits(child1Index, child2Index, i);
        }
    }
}

public int parentSelection() {
	int bestIndex = -1;
	double bestFitness = Double.MAX_VALUE;

	//create list of random indices
	int[] indices = ArrayMethods.shuffle(aiParentIndices, oRandom);

	// select from the first tournamentSize elements
	for(int i = 0; i < iTournamentSize; i++) {
		int sol = indices[i];
		double fitness = oProblem.getObjectiveFunctionValue(sol);

		// don't need to be concerned about selecting randomly from multiple best
		// solutions as the tournamentSize parents were already randomised.
		if(fitness < bestFitness) {
			bestFitness = fitness;
			bestIndex = sol;
		}
	}

	return bestIndex;
}

protected int[] getNextGeneration(SAT oProblem, int iPopulationSize) {

		// total population size is size of parent population plus size of offspring population
		int iTotalPopulationSize = iPopulationSize << 1;

		// offspring indices are from 'populationSize' inclusive to 'populationSize * 2' exclusive.
		int[] aiOffspringMemoryIndices = IntStream.range(iPopulationSize, iTotalPopulationSize).toArray();

		// see if the best solution is in the current population or offspring population
		double dBestSolutionCost = Double.MAX_VALUE;
		double dWorstOffspringCost = -Double.MAX_VALUE;
		int bestIndex = -1;
		int worstOffspringIndex = -1;

		// evaluate the objective function value (cost) of each solution from both parent and offspring populations
		for(int iMemoryIndex = 0; iMemoryIndex < iTotalPopulationSize; iMemoryIndex++) {

			double dSolutionCost = oProblem.getObjectiveFunctionValue(iMemoryIndex);

			// update index of the best solution, favouring offspring solutions
			if( dSolutionCost <= dBestSolutionCost ) {
				dBestSolutionCost = dSolutionCost;
				bestIndex = iMemoryIndex;
			}

			// keep track of the worst solution in the offspring population
			if( iMemoryIndex >= iPopulationSize && dSolutionCost > dWorstOffspringCost) {

				worstOffspringIndex = iMemoryIndex;
				dWorstOffspringCost = dSolutionCost;
			}
		}

		// if best solution is in parent population, replace worst in offspring with best from parents
		if(bestIndex < iPopulationSize) {

			aiOffspringMemoryIndices[worstOffspringIndex - iPopulationSize] = bestIndex;
		}

		// return array of memory locations for replacement
		return aiOffspringMemoryIndices;
	}

public void performMemeticInheritance(int parent1Index, int parent2Index, int child1Index, int child2Index) {
	double v1 = problem.getObjectiveFunctionValue(parent1Index);
	double v2 = problem.getObjectiveFunctionValue(parent2Index);
	int number = problem.getNumberOfMemes();
  
  // if same then choose parent randomly
	if (v1 == v2) {
		int inheritIndex = rng.nextDouble() < 0.5 ? parent1Index : parent2Index;
		for (int i = 0; i < number; i++) {
			problem.getMeme(child1Index, i).setMemeOption(problem.getMeme(inheritIndex, i).getMemeOption());
			problem.getMeme(child2Index, i).setMemeOption(problem.getMeme(inheritIndex, i).getMemeOption());
		}
  // if < choose parent 1  
	} else if (v1 < v2) {
		for (int i = 0; i < number; i++) {
			problem.getMeme(child1Index, i).setMemeOption(problem.getMeme(parent1Index, i).getMemeOption());
			problem.getMeme(child2Index, i).setMemeOption(problem.getMeme(parent1Index, i).getMemeOption());
		}
  // if < choose parent 2  
	} else {
		for (int i = 0; i < number; i++) {
			problem.getMeme(child1Index, i).setMemeOption(problem.getMeme(parent2Index, i).getMemeOption());
			problem.getMeme(child2Index, i).setMemeOption(problem.getMeme(parent2Index, i).getMemeOption());
		}
	}
}

public void runMainLoop() {
	for(int i = 0; i < POPULATION_SIZE; i+=2) {
		// select two parents. we don't care if they are the same this week
		int p1 = p1selection.parentSelection();
		int p2 = p2selection.parentSelection();

		// calculate child indices
		int c1 = i + POPULATION_SIZE;
		int c2 = c1 + 1;
			
		// apply crossover
		crossover.applyHeuristic(p1, p2, c1, c2);

		// inherit memeplex using simple inheritance method
		inheritance.performMemeticInheritance(p1, p2, c1, c2);
        
        // mutation of memeplex (innovation)
		performMutationOfMemeplex(c1);
		performMutationOfMemeplex(c2);
    
		// mutation (change iom)
		applyMutationForChildDependentOnMeme(c1, 0);
		applyMutationForChildDependentOnMeme(c2, 0);

		// local search
		applyLocalSearchForChildDependentOnMeme(c1, 1, 2);
		applyLocalSearchForChildDependentOnMeme(c2, 1, 2);
	}
		
	// perform replacement
	replacement.doReplacement(problem, POPULATION_SIZE);
}
	
	/**
	 * Applies mutation to the child dependent on its current meme option for mutation.
	 * Mapping of meme option to IOM: IntensityOfMutation <- memeOption;
	 */
public void applyMutationForChildDependentOnMeme(int childIndex, int memeIndex) {
	int iom = problem.getMeme(childIndex, memeIndex).getMemeOption();
	mutation.setMutationRate(iom);
	mutation.applyHeuristic(childIndex);
}
	
	/**
	 * Applies the local search operator to the child as specified by its current meme option.
	 */
public void applyLocalSearchForChildDependentOnMeme(int childIndex, int operatorMemeIndex, int depthOfSearchMemeIndex) {
	int option = problem.getMeme(childIndex, operatorMemeIndex).getMemeOption();
	int depth = problem.getMeme(childIndex, depthOfSearchMemeIndex).getMemeOption();
	for (int i = 0; i < depth; i++) {
		lss[option].applyHeuristic(childIndex);
	}
}

	/**
	 * Applies mutation to each meme within the memeplex of the specified solution with probability
	 * dependent on the innovation rate.
	 */
public void performMutationOfMemeplex(int solutionIndex) {
	for (int i = 0; i < problem.getNumberOfMemes(); i++){
		Meme meme = problem.getMeme(solutionIndex, i);
		int initialOption = meme.getMemeOption();
		if (rng.nextDouble() < innovationRate) {
			int newOption = rng.nextInt(meme.getTotalOptions());
			while (newOption == initialOption){
				newOption = rng.nextInt(meme.getTotalOptions());
			}
			meme.setMemeOption(newOption);
		}
	}
}