Shulou(Shulou.com)06/03 Report--

This article mainly introduces the "open source algorithm framework Open Tabu Search how to write VRPTW JAVA code", in the daily operation, I believe that many people in the open source algorithm framework Open Tabu Search how to write VRPTW JAVA code have doubts, Xiaobian consulted a variety of materials, sorted out simple and easy to use methods of operation, hope to answer the "open source algorithm framework Open Tabu Search how to write VRPTW JAVA code" doubt helpful! Next, please follow the editor to study!

Open TS algorithm framework

As meta-heuristic partners all know, we need to learn some fixed algorithm framework at the beginning, which is the theoretical basis. With the theoretical basis, we can apply these algorithm frameworks to all kinds of strange problems, and we can always get some results, whether it is good or bad.

Often a lot of people come to ask me, which algorithm is better for this question? Which framework is more appropriate for that question? At first I was very patient and said to them: there is no best, only better. Actually, no, according to my heuristic experience over the past few years, the algorithmic framework is basically not much different as long as it is in one category (such as TS and SA, LNS and ALNS, GA and AFAS, etc.). When we do algorithm development, we should focus on the derivation of some problem characteristics, or the thinking of search operators.

All right, we've gone too far... Today's topic is to share a piece of code, an open source Tabu Search framework, and how to use it for secondary development. Let's first introduce today's protagonist: Open TS. This is a java-based tabu search algorithm framework developed by Robert Harder. In his words:

Use these classes to help build a structured and efficient Java tabu search.

The package contains the various elements needed to implement a tabu search framework, which can be said to be very comprehensive. When you write tabu search-related algorithms, you only need extend-related class or implements-related interface.

This allows us to spend more time and energy on the design of operators and other problem characteristics, rather than wasting a lot of time on maintaining the algorithm framework. Of course, this framework makes the code more robust by considering a lot of general stuff and doing a lot of extra exception handling. Thus, the speed of the code may be a little bit lost.

Um... The loss I am referring to here is relative to the kind of super god-level people. After all, they write code to remove all kinds of redundant calculations and eliminate all possible factors of slow down algorithm speed. I wish they could write directly in sinks. We ordinary workers are not that good!

In short, this algorithm framework is still very powerful, usually do papers, do projects directly to do secondary development is also a good choice.

Secondary development

There are a lot of classes given above, but for a single-threaded tabu search, you don't need to use all the class, just inherit some basic elements, and then specialize them for your problem. Now I would like to introduce some of the things to be realized in the next secondary development.

1. SolutionAdapter

To solve any problem, the first step is to define the solution structure of the problem. All you need is the SolutionAdapter class of extend Open TS, in which only one member variable is:

Private double [] objectiveValue

Give the target value vector of the solution, and then you can define other variables of the problem in your own solution. Such as the storage path, other intermediate variables of the solution, and so on.

2. TabuSearchListener

This class is an interface class, and there are several abstract methods that need to be implemented, which are:

Public void newBestSolutionFound (TabuSearchEvent event) {}

When you find a global optimal solution, what you want to do can be written in it.

Public void newCurrentSolutionFound (TabuSearchEvent event) {}

What to do when finding a new current solution can be written in this function.

Public void tabuSearchStarted (TabuSearchEvent event) {

The event triggered at the beginning of the algorithm.

Public void tabuSearchStopped (TabuSearchEvent event) {}

The event triggered at the end of the algorithm.

Basically rewriting the above abstract methods will meet most of the requirements. Of course, it also defines some nonimprove-related times, which can be used as shake.

3. ObjectiveFunction

This interface is important, and you need to implement the following abstract method after inheritance:

Public double [] evaluate (Solution solution, Move proposedMove) {}

It means to evaluate the target value vector of the neighbor solution formed by the current solution solution after proposedMove, which is the objectiveValue in the previous SolutionAdapter. What does this mean? in fact, in the implementation of the algorithm, we generally do not generate a neighbor solution directly, but generate something called it. What is this? draw a picture:

The one I marked in purple is one. In short, it records some operations that need to be done on the current solution to generate the neighbor solution, such as exchange (6,15).

Therefore, every time the neighborhood is generated, the corresponding neighbor solution can be generated, and then the cost of each corresponding neighbor solution can be evaluated to compare the quality of each neighbor solution.

4. ComplexMove

For interface, the neighbor solution of the algorithm framework is obtained through the current solution + move, so the operator operator designed in your question needs to implement this interface, which has some abstract methods as follows:

Public abstract void operateOn (Solution soln)

This method actually comes from a higher level of extends, indicating that the corresponding operation is performed on the move to the soln, such as exchange (1, 2) or relocate (1, 3), and so on.

Public abstract int [] attributesDelete ()

When the move is executed, the information returned when an element is deleted is provided to the tabu list record. For example, {1, 3} means exchange 1 and 3, then the tabu list should be recorded to prevent operations such as exchange (1, 3) in subsequent iterations.

Public abstract int [] attributesInsert ()

When the move is executed, the information returned when an element is inserted is provided to the tabu list record. Similar to when it was deleted.

5. MoveManager

This is also an interface, is not very cool, only need implements-related interface to complete an algorithm, simply not too easy! It has only one abstract method:

Public Move [] getAllMoves (Solution solution) {}

This method needs to be implemented by ourselves, and it is very important because the move set generated by the operator we designed is defined here.

I think the best thing about this framework is that it manages all the move together and only needs to modify the generation rules here when making constraint changes. For example, customer I cannot insert path j, so you can apply these restrictions when you generate it here.

6. ComplexTabuList

This is a class that represents the taboo list in tabu search, where there is a multi-dimensional tabu list that can record a lot of information:

Private int [] tabuList; / / Data structure used to store list

At the same time, this class has implemented the methods of setTabu and isTabu. These two methods need to be used in conjunction with the previously set attributesInsert () and attributesDelete () methods, and if changes are made, then the corresponding parts need to be modified, especially if tabu list is to be modified.

Example

Well, the above are some simple introductions, of course, you may not feel much about this introduction, because it is difficult to understand the essence of it before it has a good overall control of the code. on the contrary, many people feel extremely cumbersome because of the huge amount of code.

After all, I don't know how to adjust other people's things in case something goes wrong. Here, in order to make you more familiar with this framework, I posted an example of using this framework to solve a VRPTW problem. This code comes from GitHub (it seems to be some major assignments for masters courses at the University of Technology in Turin, Italy. ) the original link is oma-vrptw.

Https://github.com/oma-vrptw/oma-vrptw

This code itself has a lot to learn from, for example, it implements a relocate (called SWPA MOVE in the code, but I think relocate is more appropriate) operator, which uses some of the operations we mentioned earlier to calculate the neighbor solution with O (n) complexity when evaluating a move:

How to implement an efficient heuristic algorithm? (VRPTW)

The effect of this operator is OK. In the standard example of Solomon, most of the C series can run to the best, and the speed is even faster. When you read the source code, just follow the ideas I posted above. As for the example, I have also integrated it, and I have made some changes to the source code to make it work properly (otherwise a lot of people will come to me and ask me why the code doesn't work. ), the example can be changed at the following location.

The body of a single-threaded tabu search is in the SingleThreadedTabuSearch class, where the logic for performing an iteration is written in the protected void performOneIteration () method.

In fact, if you want to write more efficiently, the move generated by each operator should customize its own separate evaluate function. In the example, only one operator is written. If move is generated by multiple operators, you need to determine which operator move belongs to, and then evaluate accordingly. You can change the evaluate function of ObjectiveFunction to the following form:

Of course, you can also modify the code in the framework to achieve more personalized features, but I don't recommend it, because if you make a mistake, you don't know where to find what others have packaged. However, you can try to modify the underlying code when you are familiar with it. I modified the tabu list because the one I gave didn't work very well.

At this point, on the "open source algorithm framework Open Tabu Search how to write VRPTW JAVA code" study is over, I hope to be able to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.