Effects in the Algorithm Performance from Problem Structure, Searching Behavior and Temperature: A Causal Study Case for Threshold Accepting and Bin-Packing

摘要

A review of state of art reveals that the characterization and analysis of the relation between problem-algorithm has been focused only on problem features or on algorithm features; or in some situations on both, but the algorithm logical is not considered in the analysis. The above for selecting an algorithm will give the best solution. However there is more knowledge for discovering from this relation. In this paper, significant features are proposed for describing problem structure and algorithm searching fluctuation; other known metrics were considered (Autocorrelation Coefficient and Length) but were not significant. A causal study case is performed for analyzing causes and effects from: Bin-Packing problem structure. Temperature, searching behavior of Threshold Accepting algorithm and final performance to solving problem instances. The proposed features permitted in the causal study to find relations cause-effect; which gave guidelines for designing a Threshold Accepting self-adaptive algorithm. Its performance outperforms to original algorithm in 74% out of 324 problem cases. The causal analysis on relevant information from problem, algorithm (both) and algorithm logical could be an important guideline to discover rules or principles over several problem domains, which permit the design of self-adaptive algorithms to give the best solution to complex problems.