Partitions optimisées selon différents critères : évaluation et comparaison

[摘要] In this article, we study and compare partitionning methods applied to a distance matrix. Given the maximum number of classes and a criterion, we build one partition optimizing this criterion for each number of classes varying from 2 to this maximum. All the studied criteria lead to NP-hard problems. The general algorithm combines optimization and metaheuristic technics to build sub-optimal solutions. Several ways to evaluate the quality of the classes and to compare partitions corresponding to different criteria are proposed. They allow to chose the best partition fitting a distance matrix and, simulating several types of metric, to designate the criterion providing generally the best results.

[学科分类] 数学（综合）

[关键词] partitionning method;combinatorial optimization;simulations