ED
E.T. Deen
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Local search approaches are often used to find solutions for optimisation problems. However, these approaches easily get stuck in local optima, who are not yet globally optimal. More complex variants of those approaches cannot always escape those local optima easily. Thus, the need for another effective technique arises. This thesis proposes such a technique: potential KPIs. A potential KPI is an addition to the objective function such that the local search algorithm accepts solutions with `potential', i.e., solutions that are closer to the global optimum in some sense.
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known. ...
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known. ...
Local search approaches are often used to find solutions for optimisation problems. However, these approaches easily get stuck in local optima, who are not yet globally optimal. More complex variants of those approaches cannot always escape those local optima easily. Thus, the need for another effective technique arises. This thesis proposes such a technique: potential KPIs. A potential KPI is an addition to the objective function such that the local search algorithm accepts solutions with `potential', i.e., solutions that are closer to the global optimum in some sense.
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known.
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known.
In this report, the bounded Maximum Parsimony distance will be considered when
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one. ...
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one. ...
In this report, the bounded Maximum Parsimony distance will be considered when
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one.
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one.