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.