Welcome‎ > ‎


We tested Jenes against a set of standard benchmarking problems, namely:
  • De Jong’s test functions
  • Royal Road Problem
  • Travel-Salesman Problem
De Jong’s test functions outline 5 optimization landscapes with different complexity. They are defined as:

Each problem is solved by adopting a BitwiseChromosome, instead of BooleanChromosome, in order to save memory and performing genetic operations faster. Indeed, we adopt an array of int, each holding 32 bits, instead of an array of booleans. The chromosome is split in octets each representing an integer value between 0 and 255. This value is after converted to a floating point number assigned to variable xi in the functions.

The second benchmark we considered is the Royal Road Problem. In this case, the goal is to find a particular pattern of bits. The last benchmark is the well known Travel-Salesman
Problem (TSP), aimed at finding the best Hamiltonian route in a weighted undirected graph. As admissible solutions are permutations, we implemented a particular class of chromosomes named PermutationChromosome, which preserves solution admissibility during genetic operations.

Benchmark problems have been implemented in Jenes, as well as in ECJ, JDEAL and GALib frameworks, adopting a coding as much as possible similar in order to make more reliable the experimental results.
JDEAL was tested with both boolean and bitwise chromosomes (JDEAL BW).

We considered different populations size (made of 100, 250, 500, 750, 1000, 2500, 5000 individuals). Each test consisted of 10 runs on a Pentium IV 2.4 GHz with 1 MB L2 cache and 1 GB Ram. Time spent by simulation is reported in Fig.1.

Fig.1 - Min/Max time spent by each run.

The overall result is reported in Fig.2 as memory occupation and execution time on average of 10 runs.

Fig.2 - Experimental results.

Regarding the behavior along the algorithm evolution, both JDEAL and ECJ show in Fig.3 a saw shaped profile for memory, growing due to unused objects left in memory before they are garbage
collected on regular basis. The overhead spent by the virtual machine to sweep memory affects time required to process generations as shown by time peaks in Fig. 4. On the contrary, JENES performance is characterized by a flat memory profile and by a almost constant execution time, entailing an efficient memory management. In this sense, JENES seems to be similar to GALib, the most efficient implementation for this benchmark. This behavior proved to be consistent over the 10 runs.

Fig. 3 - Memory usage executing first De Jong’s function with 100 individuals

Fig. 4 - Time spent executing first De Jong’s function with 100 individuals

In order to understand how frameworks behave in stressed operational conditions, we have present results as obtained by testing the same benchmark with populations made of 5000 individuals each. In Fig.5 and Fig.6, JENES again performed better than ECJ and JDEAL. The saw-shaped profile is still visible, although becoming very irregular in the case of JDEAL-bitstring, as memory goes under stress due to
physical limits. Also execution time increases, abnormally in the latter case. In order to better analyze the behavior of ECJ and JDEAL-bitwise, we magnify the time series in Fig.7. Again, we can notice peaks when garbage collection operates on memory.

Fig. 5 - Memory usage executing first De Jong’s function with 5000 individuals

Fig. 6 - Execution spent executing first De Jong’s function with 5000 individuals

Fig.7 - Detail for ECJ and JDEAL time series with 5000 individuals

Scatter plots in Fig.8 and Fig.9 are respectively related to the first De Jong’s function and TSP at different population size. In these plots we can see how JENES maintains a coherent behavior, presenting a cluster of near time/memory data points, differently by ECJ and JDEAL. Again, JENES underlines a behavior that is comparable to GALib, being slower but showing less dispersed points in time/memory usage.

Fig.8 - Scatter plot for De Jong F1

Fig.9 - Scatter plot for TSP

In summary, JENES is a programming framework for developing genetic algorithms in Java designed to pay particular attention to memory and time usage. The main feature for this purpose is the continuous reuse of individuals and populations by pooling objects in order to limit the effect of garbage collector operations on overall performances. Experimentation confirmed that this strategy can effectively address some performance issues.