Improving an existing Pareto frontier

An existing Pareto frontier can be improved by using the paretogreedy or paretogreedyr commands. The idea is to apply a perturbation on each map in the frontier. If a new map is found which has a better maximum multipoint likelihood compared to an existing map in the frontier with the same number of breakpoints, then this new map replaces the existing map in the frontier. As in the greedy command, the perturbation mechanism is to flip a subsection of the map. This process can be very long because all the possible flips are tried for each (new) map in the frontier. The process ends when no map in the frontier can be improved. It is possible to speed up this process by exploring only a subset (the most promising one) of the set of possible flips (see the Anytime parameter). Moreover, the paretogreedyr command allows to focus on a particular portion of the frontier only, in order to improve the frontier locally around the best map previously found by paretolkh.

At the end of a paretogreedy or paretogreedyr command, the heap contains all the maps in the Pareto frontier, but also the maps found during the search. The heap size depends on the last call to the paretoheapsize command (and by default, it is equal to 1024).

Thomas Schiex 2009-10-27