Since the goal of pagination is to produce good page layouts, it is necessary to specify what the goodness of a page entails. Page layout provides a way to catch and direct the user’s attention, control the order in which different parts are read and for how long time. It is also a way to visually group, divide and structure information and present it in an easily readable and aesthetically appealing way. In addition, all this must be carried out efficiently with as little waste of resources as possible.
As the literature reveals there isn’t found best solution yet for this pagination process. In literature many researchers had tried several algorithms for this problem and similar kind of space optimization problems. But there is not any solution, which utilize the space in an efficient way.
This kind of problems regarding optimization is known as NP-Hard problems. They are mathematical problems for which, even in theory, no shortcut or smart algorithm that would lead to a simple or rapid solution is possible. An algorithm for solving a NP-Hard problem can be translated into an algorithm for solving any NP-problem of the same kind. The only way to find an optimal solution for this kind of problems is to do a computationally-intensive, exhaustive analysis, in which all possible outcomes are tested. [1]
There can be pointed out 2 main best algorithms that can be used to solve the pagination problem, Simulated Annealing and Genetic Algorithm regarding pagination.
Simulated annealing (SA) is related to global optimization technique and that reach to the solution through mutating the random solution. If the energy of the current solution is lower than previous that is accepted and that technique repeated till the best solution is achieved and the energy cannot be further reduced [2].
Genetic algorithm (GA) instead of trying to optimize a single solution, works with a population of candidate solutions that are encoded as abstract solutions (called chromosomes or the genotype of the genome). The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached. [2]
Comparison of Simulated Annealing and Genetic Algorithm
Theoretically there are quite closer relatives of SA and GA and much of their difference is external. With SA there is considered on solutions, their costs, and neighbours and moves, while with GA, considered on individuals (or chromosomes), their fitness, and selection, crossover and mutation.
Basically, SA can be simulated as GA where there is one population. So there is only one individual and there is not cross over and only considered mutations.
SA creates a new solution by modifying the current solution with local mutations and GA creates solutions by crossing over two different solutions (chromosomes). When consider the pagination problem these both approaches can be contributed to best solution as with SA there can be mutate the whole solution (Eg: In newspaper section all pages as one solution) and optimize the solution and as with GA there can be considered pages as chromosomes and there can be crossed over them to optimize the space.
In both SA and GA always consider on better solutions than random solutions and reach to the best based on that. In GA children of good parents are probably good than random ones which generated by crossed over.
In GA the crossover operator matter respect to the problem [5] and in SA the energy calculation factor matters respect to the problem to generate the best solution.
SA gives a good solution during short time which cannot be further improved with time and GA takes more time to give a better solution. In pagination problem if there is generating layout in real time as online layout creation based on user search the best case is to Simulated Annealing and if the time doesn’t matter for solution there can be either used GA or SA.
In pagination problem if there are more articles or advertisements there can achieve better solution with GA than SA.
References
[1] The Internet Encyclopedia of Science. (2009, Nov.). “NP-hard Problem”, [online]. Available: http://www.daviddarling.info/encyclopedia/N/NP-hard_problem.html
[2] M. Tim Jones, “AI Application Programming”, Hingham, Massachusetts: Charles River Media, 2003.
[3] J. David Schaffer and Larry J. Eschelman. Combinatorial Optimization by Genetic Algorithms: The Value of the Genotype/Phenotype Distinction. In Rayward-Smith et al. (editors), Modern Heuristic Search Methods. John Wiley & Sons, 1996.
No comments:
Post a Comment