JAMES v1.1 released

[Herman De Beukelaer]

Version 1.1 of the JAMES framework (core, extensions and examples) has been released. Changes include a more flexible and modular way to define custom problems, using the new concrete GenericProblem class which has replaced the former abstract class AbstractProblem.

[erfan.r...@gmail.com]

Hi Herman,

Thanks for developing James. I have used it to do some tests in my research. I have found it very useful and so I would like to tell you some of my suggestion to make James even better. But first, I have to say that in my opinion, the most strength of James is the documentation. It is really helpful, insightful for using different heuristics, and full of practical examples. And my points (they are not very clear as I used James few months ago, so I can't remember the details):

1. It think James really needs a time parameters to stop the search "wherever" it is. At the moment the time parameter is a bit limited and I would suggest to investigate other time measurement approaches in Java as well.

2. It would be great to implement some common neighborhood structures like other parts of James.

3. That would be great if there is another implementation for someone who would like to run the algorithm only on one thread. In terms of performance, sometimes multi threading implementations are slightly slow. Also at the moment, the multi threading approach is implemented for only a few algorithms not all, which highlight the need to my point.

4. That would be great if there can be some parametrized neighborhood structures. Also in evaluating the objective function in each cycle, sometime calculating the difference in objective function depends on the parameter used in the neighborhood structure.

5. It would be great if the user can have more controls over the engaged algorithm in VNS algorithm such as call backs.

6. Implementation of .ToString() for the algorithms and neighborhood structures.

7. In SA algorithm, other cooling scheme implementations,

8. Population-based meta-heuristics. I know that at the moment there are a lot of packages for this purpose. But if the user can use the same framework, that would be great.

9. A parametrized evaluation class. Sometime it needs to have a table of penalties for different parts of the solution which is also is beneficial for evaluating the difference in the objective function.

10. A callback for the current neighborhood structure during the running of a multi-neighborhood algorithm.

Many thanks,

Eric

[Herman De Beukelaer]

Hi Erfan,

Thanks a lot for your appreciation and suggestions to further improve JAMES. We will definitely consider these during future development. Allow me to reply to each of your points:

1. It think James really needs a time parameters to stop the search "wherever" it is. At the moment the time parameter is a bit limited and I would suggest to investigate other time measurement approaches in Java as well.

 

Do you remember for which algorithm(s) you had issues with slow response to the imposed runtime limit? For the searches that involve one or more sub-searches, such as VNS and parallel tempering, termination requests are propagated to these sub-searches to ensure fast termination. I guess we could extend this to other algorithms, e.g. those which explore the entire neighbourhood structure in every step, such as steepest descent, tabu search and VND. When requested to terminate, these searches could abort their current step instead of exploring the remainder of the neighbourhood structure. I have created an issue on GitHub: https://github.com/hdbeukel/james-core/issues/24.

2. It would be great to implement some common neighborhood structures like other parts of James.

 

The implementation of a neighbourhood structure depends on the solution encoding. Although people often talk about similar concepts, such as 2-opt, their precise definition may be very different for specific solution encodings. Currently, JAMES contains predefined components (including several neighbourhoods) for subset selection problems (core module) and permutation problems (extensions module). We would be glad to add other common encodings and corresponding neighbourhoods to the extensions module. It would be great if the users of JAMES can contribute to this. Perhaps you can share the solution encoding and neighbourhood(s) of your application and we can discuss about how to generalize these?

3. That would be great if there is another implementation for someone who would like to run the algorithm only on one thread. In terms of performance, sometimes multi threading implementations are slightly slow. Also at the moment, the multi threading approach is implemented for only a few algorithms not all, which highlight the need to my point.

Agreed, we will provide an option for single-threaded execution in the parallel searches. See GitHub issue: https://github.com/hdbeukel/james-core/issues/25. 

 

4. That would be great if there can be some parametrized neighborhood structures. Also in evaluating the objective function in each cycle, sometime calculating the difference in objective function depends on the parameter used in the neighborhood structure.

I assume you mean parameters that change value during search; if not, you can of course just set those when creating the neighbourhood. Then how do you envision a predefined neighbourhood search to set/update the parameters of such neighbourhood? Perhaps you can provide us with an example? 

5. It would be great if the user can have more controls over the engaged algorithm in VNS algorithm such as call backs.

 

This is actually already possible. When creating the VNS algorithm, a custom local search factory can be specified. Alternatively, if you want to use the default VND as local search but with some custom settings or callbacks, you can create VNS, retrieve the default local search (VND) factory and wrap it in a customized factory. Something like this:

VariableNeighbourhoodSearch<S> search;

search = new VariableNeighbourhoodSearch<>(problem, shakingNeighs, vndNeighs);

LocalSearchFactory<S> vndFact = search.getLocalSearchFactory();

search.setLocalSearchFactory(prob -> {

    LocalSearch<S> vnd = vndFact.create(prob);

    vnd.addSearchListener(...);

    return vnd;

})

6. Implementation of .ToString() for the algorithms and neighborhood structures.

 

Agreed, see GitHub issue: https://github.com/hdbeukel/james-core/issues/26.

7. In SA algorithm, other cooling scheme implementations,

 

Currently, JAMES does not include simulated annealing. It does provide a parallel tempering search which is a (more powerful) parallel variant of SA. Nevertheless, we do plan to add SA with various cooling schemes in the future. See GitHub issue: https://github.com/hdbeukel/james-core/issues/3.

8. Population-based meta-heuristics. I know that at the moment there are a lot of packages for this purpose. But if the user can use the same framework, that would be great.

 

You are most certainly right: there are many (Java) frameworks available that focus on population based metaheuristics such as GA, ant colony and PSO, but it would be interesting to have those in the same framework. In particular, hybrid combinations are very promising, e.g. GA with a local search as mutation operator. Given that we find the time to do so, we will definitely go in this direction during future development.

9. A parametrized evaluation class. Sometime it needs to have a table of penalties for different parts of the solution which is also is beneficial for evaluating the difference in the objective function.

 

I'm sorry but I don't think I understand what you mean. If you need to store metadata in the evaluation object, you can always design your own class, as shown in several examples on the website. Could you perhaps clarify and/or give an example?

10. A callback for the current neighborhood structure during the running of a multi-neighborhood algorithm.

Agreed, see GitHub issue: https://github.com/hdbeukel/james-core/issues/27.

If you would like to continue discussion for some of these topics, please do so in a separate post per topic to keep things organized. For those points where a GitHub issue has been created, please continue discussion there instead.

Again, thanks a lot for your appreciation and useful suggestions,

Herman

[boris.a...@gmail.com]

8. Population-based meta-heuristics.

+1, This point is very strong in the james-framework, maybe a class Population<SolutionType extends Solution> extends Search<SolutionType> or class Swarm 

<SolutionType extends Solution> extends Search<SolutionType> It could be adapted in the framework.

But it would be extremely interesting to make comparisons on the same framework with local search and population metaheuristics, many combinations :D

regards :)

[Herman De Beukelaer]

Hi Boris,

You are right, we could include population based algorithms in the search hierarchy. The most suited entry point is indeed an extension of Search, say PopulationSearch, in complement to the LocalSearch subtype. Just like the high-level local search class introduces the concept of an initial and current solution the high-level population search would then manage the initial and current population. Various algorithms like GA, PSO, etc. can then be provided by implementing the searchStep() method accordingly. This is something that we certainly would like to add in future releases. Feel free to contribute!

Thanks for your appreciation,

Herman

Op maandag 21 maart 2016 17:26:43 UTC+1 schreef boris almonacid: