Hill Climbing

This is a java based implementation of the hill climbing optimization algorithm. There are two versions of hill climbing implemented: classic Hill Climbing and Hill Climbing With Random Restarts. The code is written as a framework so the optimizers supplied can be used to solve a variety of problems. Users simply need to implement a few classes that represent aspects of their problem.

A brief overview of hill climbing and be found here.

How To Use

This framework uses gradle to build javadocs and a JAR file containing the framework.

Building A JAR of The Framework

Execute the following to generate a JAR file containing the framework:

./gradlew jar

The JAR file can be found in /build/libs/.

Building The javadocs For The Framework

Execute the following to generate the javadocs for the framework:

./gradlew javadoc

The javadocs can be found in /build/docs/javadoc/.

Creating Your Optimization Problem

The HillClimb and HillClimbRandRestart classes are responsible for performing the local search/optimization using the respective algorithm they are named after. Both classes take in an problem class that implements IHillClimbProblem and a set of parameters used by the algorithms. The problem class contains an initial guess that must be a class that implements IHillClimbSolution. If HillClimbRandRestart is to be used, then a class that implements IHillClimbSolnGenerator must be created which is responsible for creating random possible solutions..

Inorder to perform a local search using HillClimb or HillClimbRandRestart you must:

1. Create a class that implements IHillClimbProblem which represents the problem being solved
2. Create a class that implements IHillClimbSolution which represents possible solutions
3. Create an instance of your problem and solution class
4. Create a instance of HillClimbParams and specify algorithm parameters
5. (Optional) - Create a class that implements IHillClimbProbGenerator if HillClimbRandRestart is being used
6. Create an instance of HillClimb or HillClimbRandRestart
7. Call the optimize() method on HillClimb or HillClimbRandRestart to being optimization

A quick abstract example on how to use the optimizer:

HillClimbParams params = new HillClimbParams();
params.setMinimization(true);
params.setGoalScore(0);
params.setMaxIterations(25);

IHillClimbProblem initialState = new SomeProblem();

HillClimb climber = new HillClimb(initialState, params);

IHillClimbSolution optimal = climber.optimize();

Implemented Local Search Problems

Each of these local search problems' have a demo implemented as a main method in their associated IHillClimbProblem implementations.

Also here is a small writeup about the steps followed to create a problem class - link.

NQueens

Given a N x N chess board containing N queens(restrict a single queen per column for simplicity), find an arrangement queens on the board such that no queen is in conflict. Queens are in conflict if they may take another, that is if two queens are in the same row or are diagonal of one another. For the supplied implementation we limit the search's branching factor by only allowing one queen to be moved at a time. For a given NQueens board we start by iterating over the columns. In each column we look at each new potential solution that can be generated by moving the queen in that column to rows it does not currently occupy. Since we iterate over each column and each row currently not occupied in that column, we end up with a N * (N-1) branching factor. That is, N * (N-1) potential solutions are generated on each iteration.

Minimizing/Maximizing A One Variable Real Valued Function

Given an one variable real valued function(R->R ex. f(x)=x, f(x)=x^2, f(x)=log(x)) find the maximum/minimum of the function. You could use this to minimize/maximize a simple function or extend the code to optimize something more complicated like a loss function for a machine learning model.