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.

为了开发一种自动设计方法的元式搜索方法，我们主要研究了最小化和验证表达式，这是计算上的困难问题之一。我们处理的表达式是exor-sum-sepructs表达式（不久的是ESOP），这些表达式是表达式，即任意产品术语是由exors组合的。我们实施了一种简单但庞大的耗时算法，将简单的简单转换规则应用于ESOP，并将ESOPS应用于ESOP，并收集了应用规则的序列，以发现有效地达到最低范围。尽管我们的目标是一种自动方法来发现有效的子序列，但我们手动发现了有效检索序列的某些特性。使用这些属性，我们开发了一种最小化ESOP的新算法：（1）提出的算法可以为所有六变量函数和某些七变量函数计算有效的最小ESOP。对于五变量的函数，到目前为止已经知道了一些有效的算法，但是尚未有六变化功能的有效算法。算法的关键点是搜索空间的修剪方法，取决于搜索参数的下层和上限。（2）开发了上述算法的一些加速方法，实验结果证明了这些方法的有效性。我们首次获得了四个基准功能的最低ESOP，CON1，MISEX1，RD53和SQRT8。在该研究项目过程中获得的一些结果已在国际会议上介绍。

项目成果

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)。