Automatic Design of Searching Algorithms in Meta-Heuristics

元启发式搜索算法的自动设计

• 批准号: 13680382
• 负责人: NISHITANI Yasuaki
• 金额: $ 1.41万
• 依托单位: Iwate University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680382/
• 关键词: meta-heuristics; algorithm; EXOR; ESOP; minimization; search; pruning; benchmark; 計算困難問題; メタヒューリスティックス; 排他的論理論; 探索アルゴリズム; 分枝限定法; 並列処理; 排他的論理和; 分岐限定法

In order to develop an automatic design method of meta-heuristics searching, we have mainly studied minimization of AND-EXOR expressions, which is one of the computationally hard problems. The expressions which we deal with are EXOR-sum-of-products expressions (shortly ESOPs) which are expressions such that arbitrary products terms are combined by EXORs.We implemented a simple but huge time consuming algorithm, which applies simple transforming rules to ESOPs repeatedly, and collected sequences of applied rules to discover subsequences to reach efficiently the minimum ESOPs. Though our goal is an automatic method to discover efficient subsequences, we found manually some properties of efficient retrieval sequences. Using these properties, we develop a new faster algorithm of minimizing ESOPs :(1) The proposed algorithm can compute efficiently exact minimum ESOPs for all six-variable functions and for some seven-variable functions. For five-variable functions, there were some efficient algorithms but no efficient algorithms for six-varible functions have been known so far. The key point of our algorithm is a pruning method of searching space, which depends on the lower and upper bounds of parameters of searching.(2) Some acceleration methods of the above algorithm are developed and experimental results demonstrate the effectiveness of these methods. For the first time, we have obtained the exactly minimum ESOPs for four benchmark functions, con1, misex1, rd53, and sqrt8.Some results obtained during the process of this research project have been presented at international conferences.

为了开发元启发式搜索的自动设计方法，我们主要研究了AND-EXOR表达式的最小化，这是计算难题之一。我们处理的表达式是 EXOR 乘积和表达式（简称 ESOP），这些表达式是通过 EXOR 组合任意乘积项的表达式。我们实现了一个简单但耗时的算法，该算法重复地将简单的转换规则应用于 ESOP ，并收集应用规则的序列来发现子序列，从而有效地达到最低 ESOP。尽管我们的目标是一种发现有效子序列的自动方法，但我们手动发现了有效检索序列的一些属性。利用这些属性，我们开发了一种新的更快的最小化 ESOP 的算法：（1）所提出的算法可以有效地计算所有六变量函数和一些七变量函数的精确最小 ESOP。对于五变量函数，存在一些有效的算法，但迄今为止还没有对于六变量函​​数的有效算法。算法的关键是搜索空间的剪枝方法，它取决于搜索参数的下界和上界。(2)开发了上述算法的一些加速方法，实验结果证明了这些方法的有效性。我们首次获得了四个基准函数 con1、misex1、rd53 和 sqrt8 的精确最低 ESOP。该研究项目过程中获得的一些结果已在国际会议上展示。

项目成果

T.Hirayama: "Minimizing AND-EXOR expressions of some benchmark functions"Proc. of 6th International Symposium on Representations and Methodology of Future Computing Technologies (RM2003). 69-76 (2003)

T.Hirayama：“最小化某些基准函数的 AND-EXOR 表达式”Proc。

R.Ishikawa: "Pseudocube-based expressions to enhance testability"Proc. of IEEE Asia-Pacific Conference on Circuits and Systems 2002. 2. 305-310 (2002)

R.Ishikawa：“基于伪立方体的表达式增强可测试性”Proc。

T.Hirayama: "A faster algorithm of minimizing AND-EXOR expressions"Proc. of IEEE Asia-Pacific Conference on Circuits and Systems 2002. 2. 293-298 (2002)

T.Hirayama：“一种更快的最小化 AND-EXOR 表达式的算法”Proc。

Hirayama, T., Sato, T., Nishitani, Y.: "Minimizing AND-EXOR expressions of some benchmark functions"Proc. Of 6th International Symposium on Representations and Methodology of Future Computing Technologies (RM2003), Trier, Germany. Mar.. (2003)

Hirayama, T.、Sato, T.、Nishitani, Y.：“最小化某些基准函数的 AND-EXOR 表达式”Proc。

T.Hirayama: "A faster algorithm of minimizing AND-EXOR expressions"IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences. E85-A・12. 2708-2714 (2002)

T. Hirayama：“最小化 AND-EXOR 表达式的更快算法”IEICE Trans 电子、通信和计算机科学基础知识 E85-A·12 (2002)。