Science BlogInstitute of Applied Optimizationhttp://iao.hfuu.edu.cn/blogs/science-blog2020-02-16T22:35:54+00:00Article "Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features" appears in Applied Soft Computing Journal2018-09-17T20:32:10+00:002018-09-17T20:32:10+00:00http://iao.hfuu.edu.cn/blogs/science-blog/158-article-automatically-discovering-clusters-of-algorithm-and-problem-instance-behaviors-as-well-as-their-causes-from-experimental-data-algorithm-setups-and-instance-features-appears-in-applied-soft-computing-journalThomas Weise<p><img src="http://iao.hfuu.edu.cn/images/publications/icons/applied_soft_computing.gif" /></p><p>Today, our article "Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features" has appeared in the <em><a href="http://www.sciencedirect.com/journal/applied-soft-computing">Applied Soft Computing</a></em> journal published by Elsevier, which describes our research topic <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=66&catid=30">Automating Scientific Research in Optimization</a>. This article maybe marks the first contribution where a significant part of the high-level work of a researcher in the fields of <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=30">optimization</a> and machine learning is automated by a process applying different machine learning steps.</p>
<p style="margin-left: 3em;">Thomas Weise, Xiaofeng Wang, Qi Qi, Bin Li, and Ke Tang. Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. <em>Applied Soft Computing Journal (ASOC)</em>, 73:366–382, December 2018.<br />doi:<a href="http://doi.org/10.1016/j.asoc.2018.08.030">10.1016/j.asoc.2018.08.030</a> / <a href="https://authors.elsevier.com/a/1Xkq85aecSZc67">share link</a> (valid until November 6, 2018)</p>
<p>In the fields of heuristic optimization, we aim to get good solutions for computationally hard problems. Solving the <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=16&catid=19">Travelling Salesman Problem</a>, for instance, means to find the shortest tour that goes through n cities and returns back to the starting point. Such problems often cannot be solved to optimality in feasible time due to their complexity. This means that algorithms often start with a more or less random initial guess about the solution and then step-by-step improve it. This means performance has two dimensions: the runtime we grant to the algorithm until we stop it and take the best-so-far result and the solution quality of that best-so-far result. Since there currently are not yet sufficient theoretical tools to assess the performance of such algorithms, researchers conduct many experiments and compare the results. This often means to apply many different setups of an algorithm to many different instances of a problem type. Since optimization algorithms are often randomized, multiple repetitions of the experiments are needed. Evaluating such experimental data is not easy. Moreover, as evaluation result, we do not just want to know which algorithm performs best and which problem is the hardest ― a researcher wants to know why.</p>
<p><img src="http://iao.hfuu.edu.cn/images/publications/icons/applied_soft_computing.gif" /></p><p>Today, our article "Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features" has appeared in the <em><a href="http://www.sciencedirect.com/journal/applied-soft-computing">Applied Soft Computing</a></em> journal published by Elsevier, which describes our research topic <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=66&catid=30">Automating Scientific Research in Optimization</a>. This article maybe marks the first contribution where a significant part of the high-level work of a researcher in the fields of <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=30">optimization</a> and machine learning is automated by a process applying different machine learning steps.</p>
<p style="margin-left: 3em;">Thomas Weise, Xiaofeng Wang, Qi Qi, Bin Li, and Ke Tang. Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. <em>Applied Soft Computing Journal (ASOC)</em>, 73:366–382, December 2018.<br />doi:<a href="http://doi.org/10.1016/j.asoc.2018.08.030">10.1016/j.asoc.2018.08.030</a> / <a href="https://authors.elsevier.com/a/1Xkq85aecSZc67">share link</a> (valid until November 6, 2018)</p>
<p>In the fields of heuristic optimization, we aim to get good solutions for computationally hard problems. Solving the <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=16&catid=19">Travelling Salesman Problem</a>, for instance, means to find the shortest tour that goes through n cities and returns back to the starting point. Such problems often cannot be solved to optimality in feasible time due to their complexity. This means that algorithms often start with a more or less random initial guess about the solution and then step-by-step improve it. This means performance has two dimensions: the runtime we grant to the algorithm until we stop it and take the best-so-far result and the solution quality of that best-so-far result. Since there currently are not yet sufficient theoretical tools to assess the performance of such algorithms, researchers conduct many experiments and compare the results. This often means to apply many different setups of an algorithm to many different instances of a problem type. Since optimization algorithms are often randomized, multiple repetitions of the experiments are needed. Evaluating such experimental data is not easy. Moreover, as evaluation result, we do not just want to know which algorithm performs best and which problem is the hardest ― a researcher wants to know why.</p>
Special Issue on Benchmarking of Computational Intelligence Algorithms in the Applied Soft Computing Journal2017-10-04T08:00:00+00:002017-10-04T08:00:00+00:00http://iao.hfuu.edu.cn/bocia-ci-siThomas Weise<div style="clear: both;"><a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf"><img style="width: 4em; height: 5.64517249em; float: right; margin-left: 1em; margin-right: 0.5em; margin-top: 0.1em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/cfp_icon.svg" alt="Call for Papers" /></a> <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf"><img style="width: 4em; height: 5.64517249em; float: left; margin-left: 0.5em; margin-right: 1em; margin-top: 0.1em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/cfp_icon.svg" alt="Call for Papers" /></a>
<p style="font-size: 120%; font-weight: bold; text-align: center;">Special Issue on Benchmarking of Computational Intelligence Algorithms</p>
<p style="font-size: 107%; font-weight: bold; text-align: center;"><a style="font-size: 107%; font-weight: bold;" href="http://www.journals.elsevier.com/applied-soft-computing/">Applied Soft Computing</a> by Elsevier B.V.<br /><a href="http://iao.hfuu.edu.cn/bocia-asoc-si">http://iao.hfuu.edu.cn/bocia-asoc-si</a></p>
<p style="clear: both;"> </p>
</div>
<p><a href="http://www.journals.elsevier.com/applied-soft-computing/"><img style="width: 6em; height: 8.15em; float: left; margin-right: 1em; margin-top: 0.3em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/asoc_journal_cover.gif" alt="Cover of the Applied Soft Computing journal." /></a>Computational Intelligence (CI) is a huge and expanding field which is rapidly gaining importance, attracting more and more interests from both academia and industry. It includes a wide and ever-growing variety of optimization and machine learning algorithms, which, in turn, are applied to an even wider and faster growing range of different problem domains. For all of these domains and application scenarios, we want to pick the best algorithms. Actually, we want to do more, we want to improve upon the best algorithm. This requires a deep understanding of the problem at hand, the performance of the algorithms we have for that problem, the features that make instances of the problem hard for these algorithms, and the parameter settings for which the algorithms perform the best. Such knowledge can only be obtained empirically, by collecting data from experiments, by analyzing this data statistically, and by mining new information from it. Benchmarking is the engine driving research in the fields of optimization and machine learning for decades, while its potential has not been fully explored. Benchmarking the algorithms of Computational Intelligence is an application of Computational Intelligence itself! This special issue of the EI/SCIE-indexed <a href="http://www.journals.elsevier.com/applied-soft-computing/">Applied Soft Computing</a> journal published by Elsevier B.V. solicits novel contributions from this domain according to the topics of interest listed below.</p>
<p style="clear: both;"><a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">Here</a> you can download the Call for Papers (<a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">CfP</a>) in <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">PDF format</a> and <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.txt">here</a> as <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.txt">plain text file</a>. The journal's website where the papers appear is <a href="https://www.sciencedirect.com/journal/applied-soft-computing/special-issue/10LQLZBS7T4">here</a>.</p>
<div style="clear: both;"><a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf"><img style="width: 4em; height: 5.64517249em; float: right; margin-left: 1em; margin-right: 0.5em; margin-top: 0.1em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/cfp_icon.svg" alt="Call for Papers" /></a> <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf"><img style="width: 4em; height: 5.64517249em; float: left; margin-left: 0.5em; margin-right: 1em; margin-top: 0.1em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/cfp_icon.svg" alt="Call for Papers" /></a>
<p style="font-size: 120%; font-weight: bold; text-align: center;">Special Issue on Benchmarking of Computational Intelligence Algorithms</p>
<p style="font-size: 107%; font-weight: bold; text-align: center;"><a style="font-size: 107%; font-weight: bold;" href="http://www.journals.elsevier.com/applied-soft-computing/">Applied Soft Computing</a> by Elsevier B.V.<br /><a href="http://iao.hfuu.edu.cn/bocia-asoc-si">http://iao.hfuu.edu.cn/bocia-asoc-si</a></p>
<p style="clear: both;"> </p>
</div>
<p><a href="http://www.journals.elsevier.com/applied-soft-computing/"><img style="width: 6em; height: 8.15em; float: left; margin-right: 1em; margin-top: 0.3em;" src="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/asoc_journal_cover.gif" alt="Cover of the Applied Soft Computing journal." /></a>Computational Intelligence (CI) is a huge and expanding field which is rapidly gaining importance, attracting more and more interests from both academia and industry. It includes a wide and ever-growing variety of optimization and machine learning algorithms, which, in turn, are applied to an even wider and faster growing range of different problem domains. For all of these domains and application scenarios, we want to pick the best algorithms. Actually, we want to do more, we want to improve upon the best algorithm. This requires a deep understanding of the problem at hand, the performance of the algorithms we have for that problem, the features that make instances of the problem hard for these algorithms, and the parameter settings for which the algorithms perform the best. Such knowledge can only be obtained empirically, by collecting data from experiments, by analyzing this data statistically, and by mining new information from it. Benchmarking is the engine driving research in the fields of optimization and machine learning for decades, while its potential has not been fully explored. Benchmarking the algorithms of Computational Intelligence is an application of Computational Intelligence itself! This special issue of the EI/SCIE-indexed <a href="http://www.journals.elsevier.com/applied-soft-computing/">Applied Soft Computing</a> journal published by Elsevier B.V. solicits novel contributions from this domain according to the topics of interest listed below.</p>
<p style="clear: both;"><a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">Here</a> you can download the Call for Papers (<a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">CfP</a>) in <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.pdf">PDF format</a> and <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.txt">here</a> as <a href="http://iao.hfuu.edu.cn/images/publications/bocia-asoc-si/bocia-asoc-si_cfp.txt">plain text file</a>. The journal's website where the papers appear is <a href="https://www.sciencedirect.com/journal/applied-soft-computing/special-issue/10LQLZBS7T4">here</a>.</p>
Research Talk: Automating Scientific Research in Optimization2017-07-09T08:08:00+00:002017-07-09T08:08:00+00:00http://iao.hfuu.edu.cn/blogs/science-blog/66-how-to-automate-scientific-research-in-optimizationThomas Weise<p><img src="http://iao.hfuu.edu.cn/images/graphics/optimizationBenchmarkingLogo.svg" /></p><p>One of my fundamental research interests is how we can determine which <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">optimization algorithm</a> is good for which problem.</p>
<p>Unfortunately, answering this question is quite complicated. For most practically relevant problems, we need to <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=30">find a trade-off</a> between the <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=29&catid=30">(run)time</a> we can invest in getting a good solution against the quality of said solution. Furthermore, the performance of almost all algorithms cannot just be a described by single pair of "solution quality" and "time needed to get a solution of that quality". Instead, these (anytime) algorithms start with an initial (often not-so-good) guess about the solution and then improve it step-by-step. In other words, their runtime behavior can be described as something like a function relating solution quality to runtime. But not a real function, since a) many algorithms are randomized, meaning that they behave differently every time you use them, even with the same input data, and b) an algorithm will usually behave different on different instances of an optimization problem type.</p>
<p>This means that we need to do a lot of experiments: We need to apply an optimization algorithm multiple times to a given optimization problem instance in order to "average out" the randomness. Each time, we need to collect data about the whole runtime behavior, not just the final results. Then we need to do this for multiple instances with different features in order to learn about how, e.g., the scale of a problem influences the algorithm behavior. This means that we will quite obtain a lot of data from many algorithm setups on many problem instances. The question that researchers face is thus "How can we extract useful information from that data?" How can we obtain information which helps us to improve our algorithms? How can we get data from which we can learn about the weaknesses of our methods so that we can improve them?</p>
<p>In this <a href="http://iao.hfuu.edu.cn/images/publications/weise_2018_automating_research_work_in_optimization_slides_1h30min.pdf">research presentation</a>, I discuss my take on this subject. I introduce a process for automatically discovering the reasons why a certain algorithm behaves as it does and why a problem instance is harder for a set of algorithms than another. This process has already been implemented in our open source <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=17&catid=19">optimizationBenchmarking.org</a> framework and is currently implemented in <code>R</code>.</p>
<p><img src="http://iao.hfuu.edu.cn/images/graphics/optimizationBenchmarkingLogo.svg" /></p><p>One of my fundamental research interests is how we can determine which <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">optimization algorithm</a> is good for which problem.</p>
<p>Unfortunately, answering this question is quite complicated. For most practically relevant problems, we need to <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=30">find a trade-off</a> between the <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=29&catid=30">(run)time</a> we can invest in getting a good solution against the quality of said solution. Furthermore, the performance of almost all algorithms cannot just be a described by single pair of "solution quality" and "time needed to get a solution of that quality". Instead, these (anytime) algorithms start with an initial (often not-so-good) guess about the solution and then improve it step-by-step. In other words, their runtime behavior can be described as something like a function relating solution quality to runtime. But not a real function, since a) many algorithms are randomized, meaning that they behave differently every time you use them, even with the same input data, and b) an algorithm will usually behave different on different instances of an optimization problem type.</p>
<p>This means that we need to do a lot of experiments: We need to apply an optimization algorithm multiple times to a given optimization problem instance in order to "average out" the randomness. Each time, we need to collect data about the whole runtime behavior, not just the final results. Then we need to do this for multiple instances with different features in order to learn about how, e.g., the scale of a problem influences the algorithm behavior. This means that we will quite obtain a lot of data from many algorithm setups on many problem instances. The question that researchers face is thus "How can we extract useful information from that data?" How can we obtain information which helps us to improve our algorithms? How can we get data from which we can learn about the weaknesses of our methods so that we can improve them?</p>
<p>In this <a href="http://iao.hfuu.edu.cn/images/publications/weise_2018_automating_research_work_in_optimization_slides_1h30min.pdf">research presentation</a>, I discuss my take on this subject. I introduce a process for automatically discovering the reasons why a certain algorithm behaves as it does and why a problem instance is harder for a set of algorithms than another. This process has already been implemented in our open source <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=17&catid=19">optimizationBenchmarking.org</a> framework and is currently implemented in <code>R</code>.</p>
Why you should use Evolutionary Algorithms to solve your optimization problems (and why not).2017-04-01T15:13:46+00:002017-04-01T15:13:46+00:00http://iao.hfuu.edu.cn/blogs/science-blog/48-why-use-evolutionary-algorithmsThomas Weise<p><a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=26&catid=20&Itemid=129">Some time ago</a>, I discussed why global optimization with an <a href="http://en.wikipedia.org/wiki/Evolutionary_Algorithm">Evolutionary Algorithm</a> (EA) is <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=26&catid=20&Itemid=129">not necessarily better than local search</a>. Actually, I get asked the question <em>"Why should I use an EA?"</em> quite a few times. Thus, today, it is time to write down a few ideas about <a href="http://iao.hfuu.edu.cn/#why">why</a> and <a href="http://iao.hfuu.edu.cn/#whyNot">why not</a> you may benefit from using an EA. I tried to be objective, which is not entirely easy since I work in that domain.</p>
<p><a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=26&catid=20&Itemid=129">Some time ago</a>, I discussed why global optimization with an <a href="http://en.wikipedia.org/wiki/Evolutionary_Algorithm">Evolutionary Algorithm</a> (EA) is <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=26&catid=20&Itemid=129">not necessarily better than local search</a>. Actually, I get asked the question <em>"Why should I use an EA?"</em> quite a few times. Thus, today, it is time to write down a few ideas about <a href="http://iao.hfuu.edu.cn/#why">why</a> and <a href="http://iao.hfuu.edu.cn/#whyNot">why not</a> you may benefit from using an EA. I tried to be objective, which is not entirely easy since I work in that domain.</p>
Intelligent Production and Logistics: The Viewpoint of Optimization2017-03-18T15:27:42+00:002017-03-18T15:27:42+00:00http://iao.hfuu.edu.cn/blogs/science-blog/43-intelligent-production-and-logistics-the-viewpoint-of-optimizationThomas Weise<p>Currently, two of the leading industry nations, Germany and China, are pushing their industry to increase a higher degree of <a href="http://en.wikipedia.org/wiki/Automation">automation</a>. Automation is among the key technologies of concepts such as <em><a href="http://en.wikipedia.org/wiki/Industry_4.0">Industry 4.0</a></em> and <em>Made in China 2025</em> [<a lang="zh_HANS" href="http://baike.baidu.com/item/%E4%B8%AD%E5%9B%BD%E5%88%B6%E9%80%A02025">中国制造2025</a>]. The goal is not automation in the traditional sense, i.e., the fixed and rigid implementation of static processes which are to be repeated millions of times in exactly the same way. Instead, <em>decisions</em> should be automated, i.e., the machinery carrying out processes in production and logistics should dynamically decide what to do based on its environment and its current situation. In other words, these machines should become intelligent.</p>
<p>As a researcher in <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=20&Itemid=129">optimization</a> and <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=20&catid=18&Itemid=127">operations research</a>, this idea is not new to me. Actually, this is exactly the goal of work and it has been the goal for the past seven decades – with one major difference: the <em>level</em> at which the automated, intelligent decision process takes place. In this article I want to shortly discuss my point of view on this matter.</p>
<p>Currently, two of the leading industry nations, Germany and China, are pushing their industry to increase a higher degree of <a href="http://en.wikipedia.org/wiki/Automation">automation</a>. Automation is among the key technologies of concepts such as <em><a href="http://en.wikipedia.org/wiki/Industry_4.0">Industry 4.0</a></em> and <em>Made in China 2025</em> [<a lang="zh_HANS" href="http://baike.baidu.com/item/%E4%B8%AD%E5%9B%BD%E5%88%B6%E9%80%A02025">中国制造2025</a>]. The goal is not automation in the traditional sense, i.e., the fixed and rigid implementation of static processes which are to be repeated millions of times in exactly the same way. Instead, <em>decisions</em> should be automated, i.e., the machinery carrying out processes in production and logistics should dynamically decide what to do based on its environment and its current situation. In other words, these machines should become intelligent.</p>
<p>As a researcher in <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=25&catid=20&Itemid=129">optimization</a> and <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=20&catid=18&Itemid=127">operations research</a>, this idea is not new to me. Actually, this is exactly the goal of work and it has been the goal for the past seven decades – with one major difference: the <em>level</em> at which the automated, intelligent decision process takes place. In this article I want to shortly discuss my point of view on this matter.</p>
Algorithm Synthesis: Deep Learning and Genetic Programming2017-02-26T05:56:09+00:002017-02-26T05:56:09+00:00http://iao.hfuu.edu.cn/blogs/science-blog/33-algorithm-synthesis-deep-learning-and-genetic-programmingThomas Weise<p>In an Inductive Program Synthesis (IPS) problem, a set of input/output data examples are given and the task is to find a program which can produce the desired outputs for the given inputs. Recently, researchers from the University of Cambridge and Microsoft Research have submitted <a href="https://openreview.net/pdf?id=ByldLrqlx">a paper</a> to the 5th International Conference on Learning Representations (<a href="http://www.iclr.cc/">ICLR'17</a>) on <em><a href="https://arxiv.org/abs/1611.01989">DeepCoder</a></em>, a new approach to IPS, i.e., to the automatic synthesis of programs. This new technology has goals similar to <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=19&catid=19&Itemid=128">our work</a> on program synthesis, but achieves them with entirely different means.</p>
<p>In an Inductive Program Synthesis (IPS) problem, a set of input/output data examples are given and the task is to find a program which can produce the desired outputs for the given inputs. Recently, researchers from the University of Cambridge and Microsoft Research have submitted <a href="https://openreview.net/pdf?id=ByldLrqlx">a paper</a> to the 5th International Conference on Learning Representations (<a href="http://www.iclr.cc/">ICLR'17</a>) on <em><a href="https://arxiv.org/abs/1611.01989">DeepCoder</a></em>, a new approach to IPS, i.e., to the automatic synthesis of programs. This new technology has goals similar to <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=19&catid=19&Itemid=128">our work</a> on program synthesis, but achieves them with entirely different means.</p>
Measuring the Runtime of (Optimization) Algorithms2017-02-16T15:47:29+00:002017-02-16T15:47:29+00:00http://iao.hfuu.edu.cn/blogs/science-blog/29-measuring-the-runtime-of-optimization-algorithmsThomas Weise<p>The main area of research of our institute is <a href="https://en.wikipedia.org/wiki/Metaheuristic">metaheuristic</a> optimization, i.e., researching algorithms that can find good approximate solutions for computationally hard problems in feasible time.</p>
<p>The <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Traveling Salesman Problem</a> (TSP) is an example for such an optimization task. In a TSP, $$n$$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is <a href="https://en.wikipedia.org/wiki/NP-hardness">NP-hard</a>, meaning that any currently known algorithm for finding the exact globally best solution for any given TSP will need a time which grows exponentially with $$n$$ in the worst case. And this is unlikely to change. In other words, if a TSP instance has $$n$$ cities, then the worst-case runtime of any exact TSP solver is in <a href="https://en.wikipedia.org/wiki/Big_O">$$O(2^n)$$</a>. Well, today we have algorithms that can exactly solve a wide range of problems with <a href="https://en.wikipedia.org/wiki/Concorde_TSP_Solver">tens of thousands</a> of nodes and approximate the solution of <a href="http://www.akira.ruc.dk/~keld/research/LKH/">million-node problems</a> with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.</p>
<p>What researchers try to do is to develop algorithms that can find tours which are as short as possible and do so as fast as possible. Here, let us look at the meaning of "fast". Fast has something to do with time. In other words, in order to know if an algorithm $$A$$ is fast, a <a href="http://coco.lri.fr/downloads/download15.02/bbobdocexperiment.pdf">common approach</a> is to measure the time that it needs to find a solution of a given quality. If that time is shorter than the time another algorithm $$B$$ needs, we can say that $$A$$ is faster than $$B$$. This sounds rather trivial, but if we take a closer look, it is actually not: There are multiple ways to measure time, and each has distinctive advantages and disadvantages.</p>
<p>The main area of research of our institute is <a href="https://en.wikipedia.org/wiki/Metaheuristic">metaheuristic</a> optimization, i.e., researching algorithms that can find good approximate solutions for computationally hard problems in feasible time.</p>
<p>The <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Traveling Salesman Problem</a> (TSP) is an example for such an optimization task. In a TSP, $$n$$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is <a href="https://en.wikipedia.org/wiki/NP-hardness">NP-hard</a>, meaning that any currently known algorithm for finding the exact globally best solution for any given TSP will need a time which grows exponentially with $$n$$ in the worst case. And this is unlikely to change. In other words, if a TSP instance has $$n$$ cities, then the worst-case runtime of any exact TSP solver is in <a href="https://en.wikipedia.org/wiki/Big_O">$$O(2^n)$$</a>. Well, today we have algorithms that can exactly solve a wide range of problems with <a href="https://en.wikipedia.org/wiki/Concorde_TSP_Solver">tens of thousands</a> of nodes and approximate the solution of <a href="http://www.akira.ruc.dk/~keld/research/LKH/">million-node problems</a> with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.</p>
<p>What researchers try to do is to develop algorithms that can find tours which are as short as possible and do so as fast as possible. Here, let us look at the meaning of "fast". Fast has something to do with time. In other words, in order to know if an algorithm $$A$$ is fast, a <a href="http://coco.lri.fr/downloads/download15.02/bbobdocexperiment.pdf">common approach</a> is to measure the time that it needs to find a solution of a given quality. If that time is shorter than the time another algorithm $$B$$ needs, we can say that $$A$$ is faster than $$B$$. This sounds rather trivial, but if we take a closer look, it is actually not: There are multiple ways to measure time, and each has distinctive advantages and disadvantages.</p>
Are Black-Box Global Search Methods, such as Metaheuristics like Evolutionary Algorithms, better than Local Search?2017-01-26T16:55:34+00:002017-01-26T16:55:34+00:00http://iao.hfuu.edu.cn/blogs/science-blog/26-global-search-vs-local-searchThomas Weise<p>Sometimes, when discussing the benefits of <a href="http://en.wikipedia.org/wiki/Evolutionary_algorithm">Evolutionary Algorithms</a> (EAs), their special variant <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">Genetic Algorithms</a> (GAs) with bit-string based search spaces, or other <a href="http://en.wikipedia.org/wiki/Metaheuristic">metaheuristic</a> <a href="http://en.wikipedia.org/wiki/Global_optimization">global search</a> algorithms, statements like the following may be made: <em>"If you use a <span style="color: red;">huge (unlimited) population size</span> with a <span style="color: blue;">large running budget (unlimited iterations or generations)</span> for both global search metaheuristics (<span style="color: green;">with enough diversity</span>) and <a href="http://en.wikipedia.org/wiki/Local_search_%28optimization%29">local search</a> metaheuristics, the <strong>global search approach will no doubt <span style="color: violet;">outperform</span> the local search</strong>."</em></p>
<p>I cannot not really agree to this statement, in particular if it is applied to <em>black box</em> metaheuristics (those that make no use of the problem knowledge).</p>
<p>This post here is heavily related to the following paper:</p>
<p style="margin-left: 1.5em;">Thomas Weise, Yuezhong Wu, Raymond Chiong, Ke Tang, and Jörg Lässig. Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. <em>Journal of Global Optimization</em> 66(3):511-534, November 2016.<br />doi:<a href="http://dx.doi.org/10.1007/s10898-016-0417-5">10.1007/s10898-016-0417-5</a> / <a href="http://iao.hfuu.edu.cn/images/publications/WWCTL2016GVLSTIOPSOEAP.pdf">pdf</a></p>
<p>I will begin with a quick introduction to the concepts of local search, EAs, and black-box global search metaheuristics. Then I will take apart the different assumptions in the statement above (highlighted with different colors) step-by-step. I make what I think is a good case against the assumption of superior performance of pure global optimization methods like EAs. That being said, I conclude by pointing out practitioners rarely use pure EAs – the best performing methods are hybrid algorithms that combine the speed of a local search with the resilience against getting stuck at local optima offered by global search.</p>
<p>Sometimes, when discussing the benefits of <a href="http://en.wikipedia.org/wiki/Evolutionary_algorithm">Evolutionary Algorithms</a> (EAs), their special variant <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">Genetic Algorithms</a> (GAs) with bit-string based search spaces, or other <a href="http://en.wikipedia.org/wiki/Metaheuristic">metaheuristic</a> <a href="http://en.wikipedia.org/wiki/Global_optimization">global search</a> algorithms, statements like the following may be made: <em>"If you use a <span style="color: red;">huge (unlimited) population size</span> with a <span style="color: blue;">large running budget (unlimited iterations or generations)</span> for both global search metaheuristics (<span style="color: green;">with enough diversity</span>) and <a href="http://en.wikipedia.org/wiki/Local_search_%28optimization%29">local search</a> metaheuristics, the <strong>global search approach will no doubt <span style="color: violet;">outperform</span> the local search</strong>."</em></p>
<p>I cannot not really agree to this statement, in particular if it is applied to <em>black box</em> metaheuristics (those that make no use of the problem knowledge).</p>
<p>This post here is heavily related to the following paper:</p>
<p style="margin-left: 1.5em;">Thomas Weise, Yuezhong Wu, Raymond Chiong, Ke Tang, and Jörg Lässig. Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. <em>Journal of Global Optimization</em> 66(3):511-534, November 2016.<br />doi:<a href="http://dx.doi.org/10.1007/s10898-016-0417-5">10.1007/s10898-016-0417-5</a> / <a href="http://iao.hfuu.edu.cn/images/publications/WWCTL2016GVLSTIOPSOEAP.pdf">pdf</a></p>
<p>I will begin with a quick introduction to the concepts of local search, EAs, and black-box global search metaheuristics. Then I will take apart the different assumptions in the statement above (highlighted with different colors) step-by-step. I make what I think is a good case against the assumption of superior performance of pure global optimization methods like EAs. That being said, I conclude by pointing out practitioners rarely use pure EAs – the best performing methods are hybrid algorithms that combine the speed of a local search with the resilience against getting stuck at local optima offered by global search.</p>
What is Optimization?2017-01-17T10:15:24+00:002017-01-17T10:15:24+00:00http://iao.hfuu.edu.cn/blogs/science-blog/25-what-is-optimizationThomas Weise<p>The center of the research of our institute is optimization. But what is optimization? Basically, <em>optimization is the art of making good decisions</em>. It provides us with a set of tools, mostly from the areas of computer science and mathematics, which are applicable in virtually all fields ranging from business, industry, biology, physics, medicine, data mining, engineering, to even art.</p>
<p>Every question that asks for a thing with a superlative feature is an optimization problem. Constructing the fastest car, finding the most profitable investment plan, finding a way to discover diseases as early and reliable as possible, scheduling your work so that you have the most spare time left for gaming – all of these are optimization tasks.</p>
<p>In this article, we will explore what an optimization problem in more detail, we will distinguish hard from easy problems and discuss what implications come from "hardness". We will discuss how exact and approximate algorithms tackle hard problems, give a slightly more formal definition of optimization problem, and list some more examples for optimization tasks. (Additionally, we also have a course on "<a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">Metaheuristic Optimization</a>" and you can find all its <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">slides here</a>.)</p>
<p>The center of the research of our institute is optimization. But what is optimization? Basically, <em>optimization is the art of making good decisions</em>. It provides us with a set of tools, mostly from the areas of computer science and mathematics, which are applicable in virtually all fields ranging from business, industry, biology, physics, medicine, data mining, engineering, to even art.</p>
<p>Every question that asks for a thing with a superlative feature is an optimization problem. Constructing the fastest car, finding the most profitable investment plan, finding a way to discover diseases as early and reliable as possible, scheduling your work so that you have the most spare time left for gaming – all of these are optimization tasks.</p>
<p>In this article, we will explore what an optimization problem in more detail, we will distinguish hard from easy problems and discuss what implications come from "hardness". We will discuss how exact and approximate algorithms tackle hard problems, give a slightly more formal definition of optimization problem, and list some more examples for optimization tasks. (Additionally, we also have a course on "<a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">Metaheuristic Optimization</a>" and you can find all its <a href="http://iao.hfuu.edu.cn/index.php?option=com_content&view=article&id=61&catid=23">slides here</a>.)</p>