Yashvardhan Sharma / Jun 20 2019
Remix of Julia by Nextjournal

Unconstrained version of Charibde in julia


Hi, I am Yashavardhan Sharma and I am selected as a student developer in Julia source of Contribution (JSOC) this year and going to spend my summer to work on the project named as Implementation of Charibde: A cooperative approach for optimisation. The project comes under Julia Numerics and the project is under mentorship of David P. Sanders.

What is Charibde and from where it took birth?

There's a very famous saying, "solution of great problem come from day to day life", isnt it? Imagine, you are given a task which is quite tedious and difficult to complete by one worker and luckily to solve it you also have two best workers and with them you are asked to return the output in minimum time, obviously the best technique to make it done is to harness the power of these both workers in parallel which allows the task to be completed more quickly. This is the key idea behind the technique which is proposed and implemented by Charlie Vanaret in Ocaml in its Phd thesis for difficult global optimising problems (to find minimum or maximum of the given objective function in given domain) and named it Charibde: a Cooperative Approach.

Detailed Charibde

Charibde is a synergetic scheme aimed to establish cooperation between the two approaches in order to benefit from their advantages:

1. quickly explore the search space;

2. avoid being trapped in local minima;

3. eliminate subspaces that are not feasible;

4. Certify the optimality of the solution;

Interval-based method is the only rigorous approach to achieve a numerical proof of optimality in global optimisation that interleave branching of the search-space and pruning out the subdomains that cannot contain an optimal solution. Generally, state-of-the-art solvers integrate local optimisation algorithms to compute a good upper bound of the global minimum over each subspace. Charibde propose a cooperative framework in which interval methods cooperate with evolutionary algorithms to enhance the pruning of the search-space.

Within our cooperative solver Charibde, the evolutionary algorithm and the interval-based algorithm run in parallel and exchange bounds, solutions and search-space in an advanced manner via message passing.

Our hybrid algorithm Charibde (Cooperative Hybrid Algorithm using Reliable Interval-Based Methods and Differential Evolution) combines DE and a IBC algorithm. Although incorporating stochastic components, Charibde is a totally reliable solver.

Interval branch & Contract Algorithm : The goal of the algorithm is to find a value x that maximizes or minimizes the value of a real-valued function f(x), called an objective function, among some set S of admissible, or candidate solutions. The set S is called the search space, or feasible region. It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching. And reducing this search space because of the given constraints in the problem is called contraction.

Differential Algorithm : A basic DE algorithm works by having a population of candidate solutions (called individuals). These individuals are moved around in the search-space by using simple mathematical formulae to combine the positions of existing agents from the population. If the new position of an agent is an improvement then it is accepted and forms part of the population, otherwise the new position is simply discarded. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered.

Work done and remaining till now.

Implementation of Charibde has been made in julia package named CharibdeOptim for unconstraint optimisation.

The package exports three functions named ibc_minimise, diffevol_minimise, charibde_min which takes objective function and domain or search space in form of Interval or IntervalBox as arguments.

  1. ibc_minimise returns a tuple containing a closed interval of very less size having global minimum in it and IntervalBoxes whose each box of very tiny size of it represents a point where this global minimum occurred of the objective function, whereas
  2. diffevol_minimise also returns a tuple containing global minimum and the vectors which represents solution points of the objective function and
  3. charibde_min returns output in same form as ibc_minimise returns.

ibc_minimise and diffevol_minimise implements Interval Branch & Contract and Differential Evolution algorithm, these both algorithms can be used(Non-parallel version) by calling there respected functions.

charibde_min implements Charibde, it makes run both functions (ibc_minimise and diffevol_minimise)on two different worker processes in parallel and make them able to contact through remote channels.

Running charibde_min is little bit different form ibc_minimise and diffevol_minimise .We have to do things in given order before calling charibde_min;

  1. We need to launch 2 worker processes on which those two algorithms can run in parallel through "addprocs(2)" which is exported by package "Distributed";
  2. And, load CharibdeOptim on those two launched worker processes through macro "@everywhere" by command "@everywhere using CharibdeOptim".

using Distributed
2-element Array{Int64,1}: 2 3
@everywhere using CharibdeOptim
@everywhere using IntervalArithmetic
ibc_minimise((x,y)->x^2 + y^2, IntervalBox(2..3, 3..4))
([13, 13.0046], IntervalBox{2,Float64}[[2, 2.00091] × [3, 3.00091], [2.0009, 2.00183] × [3, 3.00091]])

diffevol_minimise((x,y)->x^2+y+1, IntervalBox(1..2, 2..3))
(4.0, [1.0, 2.0])
charibde_min((x,y)->x^2+y+1, IntervalBox(1..2, 2..3))
([4, 4.00009], IntervalBox{2,Float64}[[1, 1.00091] × [2, 2.00091]])

This version of Charibde can only handle unconstrained optimisation problem, in next few weeks I have to develop the package to handle constraint optimisation problem also.