Towards faster convergence of evolutionary multi-criterion optimization algorithms using Karush Kuhn Tucker optimality based local search

Evolutionary multi-criterion optimization (EMO) algorithms emphasize non-dominated and less crowded solutions in a population iteratively until the population converges close to the Pareto optimal set. During the search process, non-dominated solutions are differentiated only by their local crowding or contribution to hypervolume or using a similar other metric. Thus, during evolution and even at the final iteration, the true convergence behavior of each non-dominated solutions from the Pareto optimal set is unknown. Recent studies have used Karush Kuhn Tucker (KKT) optimality conditions to develop a KKT Proximity Measure (KKTPM) for estimating proximity of a solution from Pareto optimal set for a multi-objective optimization problem. In this paper, we integrate KKTPM with a recently proposed EMO algorithm to enhance its convergence properties towards the true Pareto optimal front. Specifically, we use KKTPM to identify poorly converged non-dominated solutions in every generation and apply an achievement scalarizing function based local search procedure to improve their convergence. Assisted by the KKTPM, the modified algorithm is designed in a way that maintains the total number of function evaluations as low as possible while making use of local search where it is most needed. Simulations on both constrained and unconstrained multi- and many objectives optimization problems demonstrate that the hybrid algorithm significantly improves the overall convergence properties. This study brings evolutionary optimization closer to mainstream optimization field and should motivate researchers to utilize KKTPM measure further within EMO and other numerical optimization algorithms.     

A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment

The single-robot search problem in an unknown environment is defined as the problem of finding a stationary object in the environment whose map is not known a priori. Compared to exploration, the only difference lies in goal selection as the objectives of search and exploration are dissimilar, i.e. a trajectory that is optimal in exploration does not necessarily minimize the expected value of the time to find an object along it. For this reason, in this paper we extend the preliminary ideas presented in Kulich et al. [1] to a general framework that accounts for the particular characteristics of the search problem. Within this framework, an important decision involved in the determination of the trajectory can be formulated as an instance of the Graph Search Problem (GSP), a generalization of the well-known Traveling Deliveryman Problem (TDP) which has not received much attention in the literature. We developed a tailored Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic for the GSP, which generates good quality solutions in very short computing times and is incorporated in the overall framework. The proposed approach produces very good results in a simulation environment, showing that it is feasible from a computational standpoint and the proposed strategy outperforms the standard approaches.     

信息共享的记忆被囊群算法

针对基本被囊群算法求解精度较低、收敛速度较慢、容易陷入局部最优的缺陷,提出信息共享的记忆被囊群算法.首先,将整个种群分为执行信息共享搜索和喷气推进搜索两个子群,引入动态自适应调整策略,用于平衡算法的全局开拓能力和局部开发能力.然后,在执行信息共享搜索模式时,部分个体向同伴所在领域相互获取信息,实现种群个体之间信息的充分交流与共享.另一部分个体引入历史最优位置,用于引导学习,增强算法搜索的有效性.在20个基准测试函数上的实验表明,文中算法的收敛速度、求解精度、鲁棒性等都较优.     

Automatic recognition of handwritten medical forms for search engines

A new paradigm, which models the relationships between handwriting and topic categories, in the context of medical forms, is presented. The ultimate goals are: (1) a robust method which categorizes medical forms into specified categories, and (2) the use of such information for practical applications such as an improved recognition of medical handwriting or retrieval of medical forms as in a search engine. Medical forms have diverse, complex and large lexicons consisting of English, Medical and Pharmacology corpus. Our technique shows that a few recognized characters, returned by handwriting recognition, can be used to construct a linguistic model capable of representing a medical topic category. This allows (1) a reduced lexicon to be constructed, thereby improving handwriting recognition performance, and (2) PCR (Pre-Hospital Care Report) forms to be tagged with a topic category and subsequently searched by information retrieval systems. We present an improvement of over 7% in raw recognition rate and a mean average precision of 0.28 over a set of 1,175 queries on a data set of unconstrained handwritten medical forms filled in emergency environments. This work was supported by the National Science Foundation.     

Scaling of program functionality

The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain convergence theorems to give general upper bounds on the length of programs needed for convergence. How big programs need to be to approach the limit depends on the type of the computer they run on. We give bounds (exponential in N, N log N and smaller) for five computer models: any, average or amorphous or random, cyclic, bit flip and four functions (AND, NAND, OR and NOR). Programs can be treated as lookup tables which map between their inputs and their outputs. Using this we prove similar convergence results for the distribution of functions implemented by linear computer programs. We show most functions are constants and the remainder are mostly parsimonious. The effect of ad-hoc rules on genetic programming (GP) are described and new heuristics are proposed. We give bounds on how long programs need to be before the distribution of their functionality is close to its limiting distribution, both in general and for average computers. The computational importance of destroying information is discussed with respect to reversible and quantum computers. Mutation randomizes a genetic algorithm population in generations. Results for average computers and a model like genetic programming are confirmed experimentally.     

分段路径寻优算法研究及实现*

传统的路径寻优只考虑了起点和终点,不能满足一些用户的实际需求;研究了一类带有必经节点序列和避开节点序列的路径寻优问题。首先将必经节点序列进行有序调整,然后根据避开节点序列和调整后的必经节点序列进行分段路径寻优,最后生成满足用户要求的最短路径。将其应用到面向手机用户的路径诱导业务中,取得了良好的效果。     

On the structure of systematic prefix codes

Systematic prefix codes play an important role in coding theory, we relate them with the problem of the partition of a free (sub-) monoid into two free sub-monoids. We show too that among the dual codes of a systematic prefix code A there exists one and only one which appears in the automaton recognizing A ^*. The characterization of this automaton and some corollaries stated here will allow us to show in further note that systematic prefix codes are involved in the structure of any regular prefix code. Work done under CNR contract No. R-l7-02-417-0-A.     

Search advertising placement strategy: Exploring the efficacy of the conventional wisdom

Search advertising is one of the most important forms of electronic commerce. While click-through rates are considered a key measure of search advertising effectiveness by search providers, brand attention can also be a valuable objective. Our paper reports on an experiment that investigated how search advertisement placement affected search users’ brand recall and recognition. The results showed that semantically associated search ads generated significantly higher levels of brand attention than contextually associated ones. Significant interaction effects were found among search ad position, keyword association, and search result quality. Implications for decision makers are discussed.     

新的混合智能优化算法及其多目标优化应用

针对人工鱼群算法后期收敛速度较慢、解精度不高的不足,按照分阶段寻优和变参数寻优的改进策略,并结合禁忌搜索算法中的相关规则,提出一种新的混合智能优化算法。该算法将寻优过程分为锁定最优解或者局部解邻域和求得高精度最优解两个阶段,每个阶段设置不同的参数并结合禁忌搜索算法以提高收敛速度和最优解精度。典型函数验证表明,该算法收敛速度快、精度高;同时,对于多目标优化问题,该算法可以提高Pareto最优解集质量,扩大决策分布范围,维持决策多样性,有利于决策者作出决策。     

改进的Dijkstra算法在灾害决策系统中的应用

灾害决策系统中,核心安置点的选择对救灾工作效率影响重大;分析常用的最短路径搜索方法,选用Dijkstra算法并对其进行改进,计算选取到达最远安置点最近的安置点作为核心安置点。实验结果表明,该方法具有良好的实用性。