According to Wikipedia, “a heuristic is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals”. As a developer, you may use a heuristic when there’s no other way to solve the problem - when you cannot find a propper algorithm to solve it.
Take the backpack’s problem for instance: you have a backpack which can hold 10 units of weight and 5 objects of weights: 2, 2, 3, 4 and 5. How do you fill the backpack best? A method is to order the objects decreasingly and keep adding them until you cannot add another one. You then have 5, 4, 3, 2 and 2. Take the first two and you filled the backpack 9/10, but really you could have filled it 10/10 by taking 5, 3 and 2. Of course, the problem becomes much more complicated when you have thousands of objects.
Eva is an simple framework which you can use to get a satisfying solution for this kind of problems. It’s intended to be usable by everyone, unlike other frameworks which require solid knowledge in the field of genetic algorithms.
See more details about how it works on the project’s site.
Assume you have a backpack which can hold 100 units and 10 objects with the following weights:
12 31 16 42 41 27 63 76 67 46
In the backpack’s problem the solution is an array or 0’s and 1’s corresponding to each object: 1 - taken, 0 - left out
One solution for this input would be
0 1 0 1 0 1 0 0 0 0
So we take the objects with weights: 31, 42 and 27 to fill the backpack.
Note that it is not mandatory to add any conditions, but it’s recommended to specify at least the above condition if you don’t want a long execution time. It is not guaranteed that the found solution will meet the specified Conditon (although ideally it should).
The idea of the Condition is to make the algorithm faster by stopping it when it finds a satisfactory solution.
The maximum number of iterations performed is number of generations times population size and a Condition cannot add iterations (i.e. iterate until a good solution is found) because there are big chances of creating an infinite or really really long run.
In this backpack example,
Solution.isAcceptable() only checks if the total weight is in the following interval: (0, backpackWeight]. You could add more conditions to always get a solution with total weight, say, over 50%.
com.amihaiemil.eva.Conditions to specify more conditions, like this:
If you specify more conditions you minimize the chances of the algorithm skipping a really good solution.