Heuristic algorithms - Revision history

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:44:53Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:44, 15 December 2024
Line 206:		Line 206:

	The tabu list above has two impacts on the algorithm. First, it prevents the algorithm from making any choice already chosen, which leads into cycling. Second, it makes the algorithms "flexible" to not always choose the optimal neighborhood solution, which allow exploring the suboptimal space. It is suitable for large and complex problems, but it is more computationally intensive and requires careful parameter tuning. For small and scalable problem, '''Hill Climbing''' is a simpler version.		The tabu list above has two impacts on the algorithm. First, it prevents the algorithm from making any choice already chosen, which leads into cycling. Second, it makes the algorithms "flexible" to not always choose the optimal neighborhood solution, which allow exploring the suboptimal space. It is suitable for large and complex problems, but it is more computationally intensive and requires careful parameter tuning. For small and scalable problem, '''Hill Climbing''' is a simpler version.



	'''Overview:'''		'''Overview:'''

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:44:22Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:44, 15 December 2024
Line 75:		Line 75:
	\|0.5		\|0.5
	\|}		\|}



	'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''		'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''
Line 86:		Line 88:
	3) Repeat until all cities are visited.		3) Repeat until all cities are visited.

	4) Return to the starting city.		4) Return to the starting city.
	~~'''Step-by-Step Solution:'''~~


	'''Step-by-Step Solution:'''		'''Step-by-Step Solution:'''
Line 143:		Line 146:

	4) Repeating until a stopping criterion is met.		4) Repeating until a stopping criterion is met.



	'''Step-by-Step Solution:'''		'''Step-by-Step Solution:'''
Line 209:		Line 214:

	3) Repeating until a stopping criterion is met.		3) Repeating until a stopping criterion is met.



	'''Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.'''		'''Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.'''

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:43:31Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:43, 15 December 2024
Line 75:		Line 75:
	\|0.5		\|0.5
	\|}		\|}



	'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''		'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:43:15Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:43, 15 December 2024
Line 128:		Line 128:

	Total distance: 80		Total distance: 80



	'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''		'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:43:00Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:43, 15 December 2024
Line 75:		Line 75:
	\|0.5		\|0.5
	\|}		\|}

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem (TSP) */

2024-12-15T22:42:35Z

Numerical Example: Traveling Salesman Problem (TSP)

← Older revision		Revision as of 18:42, 15 December 2024
Line 47:		Line 47:
	== Numerical Example: '''Traveling Salesman Problem (TSP)''' ==		== Numerical Example: '''Traveling Salesman Problem (TSP)''' ==
	The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.		The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.

	{\| class="wikitable"		{\| class="wikitable"
	\|+Distance Matrix		\|+Distance Matrix
Line 74:		Line 75:
	\|0.5		\|0.5
	\|}		\|}


	'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''		'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''

Line 85:		Line 88:

	4) Return to the starting city.		4) Return to the starting city.
			'''Step-by-Step Solution:'''

	'''Step-by-Step Solution:'''		'''Step-by-Step Solution:'''
Line 118:		Line 122:
	Total distance: 65		Total distance: 65

			* '''Return to City A:'''
	'''Return to City A:'''

	Path: A → B → D → C → A		Path: A → B → D → C → A

	Total distance: 80		Total distance: 80



	'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''		'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem(TSP) */

2024-12-15T22:41:40Z

Numerical Example: Traveling Salesman Problem(TSP)

← Older revision		Revision as of 18:41, 15 December 2024
Line 45:		Line 45:
	[[File:Screenshot 2024-12-14 213250.png\|center\|thumb\|400x400px\|Figure 5. Simulated Annealing Algorithm Steps]]		[[File:Screenshot 2024-12-14 213250.png\|center\|thumb\|400x400px\|Figure 5. Simulated Annealing Algorithm Steps]]

	== Numerical Example: '''Traveling Salesman Problem(TSP)''' ==		== Numerical Example: '''Traveling Salesman Problem (TSP)''' ==
	The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.		The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.
	{\| class="wikitable"		{\| class="wikitable"
Line 85:		Line 85:

	4) Return to the starting city.		4) Return to the starting city.


	'''Step-by-Step Solution:'''		'''Step-by-Step Solution:'''

	'''Start at City A:'''		* '''Start at City A:'''

	Unvisited: {B,C,D}		Unvisited: {B,C,D}
Line 99:		Line 98:
	Total distance: 10		Total distance: 10

			* '''Move to City B:'''
	'''Move to City B:'''

	Unvisited: {C,D}		Unvisited: {C,D}
Line 110:		Line 108:
	Total distance: 35		Total distance: 35

			* '''Move to City D:'''
	'''Move to City D:'''

	Unvisited: {C}		Unvisited: {C}
Line 129:		Line 126:


	The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.
			'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''




Line 143:		Line 143:

	4) Repeating until a stopping criterion is met.		4) Repeating until a stopping criterion is met.


	'''Step-by-Step Solution:'''		'''Step-by-Step Solution:'''

	'''Initialization:'''		* '''Initialization:'''

	Initial Path: A → B → C → D → A		Initial Path: A → B → C → D → A
Line 155:		Line 154:
	Tabu List: [ ] (empty)		Tabu List: [ ] (empty)

			* '''Generating neighborhood solutions:'''
	'''Generating neighborhood solutions:'''

	Neighborhood solutions are created by swapping the order of two cities in the current path (excluding A, the starting city). For the initial path A→B→C→D→A, the possible swaps are:		Neighborhood solutions are created by swapping the order of two cities in the current path (excluding A, the starting city). For the initial path A→B→C→D→A, the possible swaps are:
Line 166:		Line 164:
	3. Swap C and D d = 80 (Best)		3. Swap C and D d = 80 (Best)

			* '''Select the best Neighbor that not in the Tabu List'''
	'''Select the best Neighbor that not in the Tabu List'''

	Swap C and D is the best Neighbor solution		Swap C and D is the best Neighbor solution
Line 173:		Line 170:
	New Tabu List: [(C,D)]		New Tabu List: [(C,D)]

			* '''Repeat Process:'''
	'''Repeat Process:'''

	New Path: A → B → D → C → A		New Path: A → B → D → C → A
Line 182:		Line 178:
	Tabu List: [(C,D)]		Tabu List: [(C,D)]

			* '''Generating neighborhood solutions'''
	'''Generating neighborhood solutions'''

	Notice (C,D) is in Tabu List, so swapping C and D is not a viable option here.		Notice (C,D) is in Tabu List, so swapping C and D is not a viable option here.
Line 191:		Line 186:
	2. Swap B and D d = 95		2. Swap B and D d = 95

			* '''Select the best Neighbor that not in the Tabu List'''
	'''Select the best Neighbor that not in the Tabu List'''

	1. Swap B and C is the best Neighbor solution		1. Swap B and C is the best Neighbor solution
Line 200:		Line 194:
	…		…

	By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and reach the final solution which is 80.
			'''By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and reach the final solution which is 80.'''


Line 215:		Line 210:
	3) Repeating until a stopping criterion is met.		3) Repeating until a stopping criterion is met.

			'''Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.'''
	Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.

	==Applications==		==Applications==
	Heuristic algorithms are extensively applied to optimize processes and solve computationally problems in IT field. They are used in network design and routing, where algorithms like A-star and Dijkstra help determine the most efficient paths for data transmission in communication networks. Cloud computing benefits from heuristics for resource allocation and load balancing, ensuring optimal distribution of tasks.<ref>Guo, Lizheng, et al. "Task scheduling optimization in cloud computing based on heuristic algorithm." ''Journal of networks'' 7.3 (2012): 547.</ref>		Heuristic algorithms are extensively applied to optimize processes and solve computationally problems in IT field. They are used in network design and routing, where algorithms like A-star and Dijkstra help determine the most efficient paths for data transmission in communication networks. Cloud computing benefits from heuristics for resource allocation and load balancing, ensuring optimal distribution of tasks.<ref>Guo, Lizheng, et al. "Task scheduling optimization in cloud computing based on heuristic algorithm." ''Journal of networks'' 7.3 (2012): 547.</ref> Moreover, heuristic algorithms also thrive in numerous domains. In biology, heuristics approaches, like asBLAST and FASTA, are used to solve problems such as DNA and specific protein comparing.<ref>Chauhan, Shubhendra Singh, and Shikha Mittal. "Exact, Heuristics and Other Algorithms in Computational Biology." ''Bioinformatics and Computational Biology''. Chapman and Hall/CRC, 2023. 38-51.</ref> Heuristic algorithms are also instrumental in finance, optimizing the portfolios to balance risk and payback. <ref>Gilli, Manfred, Dietmar Maringer, and Peter Winker. "Applications of heuristics in finance." ''Handbook on information technology in finance'' (2008): 635-653.</ref>

	Moreover, heuristic algorithms also thrive in numerous domains. In biology, heuristics approaches, like asBLAST and FASTA, are used to solve problems such as DNA and specific protein comparing.<ref>Chauhan, Shubhendra Singh, and Shikha Mittal. "Exact, Heuristics and Other Algorithms in Computational Biology." ''Bioinformatics and Computational Biology''. Chapman and Hall/CRC, 2023. 38-51.</ref> Heuristic algorithms are also instrumental in finance, optimizing the portfolios to balance risk and payback. <ref>Gilli, Manfred, Dietmar Maringer, and Peter Winker. "Applications of heuristics in finance." ''Handbook on information technology in finance'' (2008): 635-653.</ref>

	==Conclusion==		==Conclusion==
	Heuristic algorithms are widely applied in solving complex optimization problems where finding an exact solution is computationally infeasible. These algorithms use problem-specific strategies to explore the solution space efficiently, often arriving at near-optimal solutions in a fraction of the time required by exact methods.		Heuristic algorithms are widely applied in solving complex optimization problems where finding an exact solution is computationally infeasible. These algorithms use problem-specific strategies to explore the solution space efficiently, often arriving at near-optimal solutions in a fraction of the time required by exact methods. While heuristic algorithms may not always guarantee the optimal solution, their efficiency, scalability, and flexibility make them an important tool for those challenges in real world. These options allow us to make a call of compromise between computational feasibility and solution quality. As technology advances and problems grow in complexity, heuristic algorithms will continue to evolve to delve and improvise more potential in optimization.

	While heuristic algorithms may not always guarantee the optimal solution, their efficiency, scalability, and flexibility make them an important tool for those challenges in real world. These options allow us to make a call of compromise between computational feasibility and solution quality. As technology advances and problems grow in complexity, heuristic algorithms will continue to evolve to delve and improvise more potential in optimization.

	==References==		==References==
	<references />		<references />

Fall2024 Team24: /* Numerical Example: Traveling Salesman Problem(TSP) */

2024-12-15T05:20:30Z

Numerical Example: Traveling Salesman Problem(TSP)

← Older revision		Revision as of 01:20, 15 December 2024
Line 200:		Line 200:
	…		…

	By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and ~~we get our~~ final solution which is 80.		By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and reach the final solution which is 80.

Fall2024 Team24 at 05:18, 15 December 2024

2024-12-15T05:18:42Z

Show changes

Fall2024 Team24: /* Popular Heuristic Algorithms */

2024-12-15T02:34:57Z

Popular Heuristic Algorithms

← Older revision		Revision as of 22:34, 14 December 2024
Line 23:		Line 23:
	* '''Metaheuristics''', such as simulated annealing or genetic algorithms, tackle the TSP by employing high-level strategies to explore the solution space more broadly and escape local optima. These methods balance global search space exploration with local exploitation of promising regions, allowing for a more thorough search for better solutions. They iteratively improve the solution while occasionally considering less favorable configurations to avoid being confined to suboptimal areas. By guiding the search process intelligently, metaheuristics adapt dynamically and effectively solve the TSP, often producing near-optimal solutions even for large-scale or complex problem instances.		* '''Metaheuristics''', such as simulated annealing or genetic algorithms, tackle the TSP by employing high-level strategies to explore the solution space more broadly and escape local optima. These methods balance global search space exploration with local exploitation of promising regions, allowing for a more thorough search for better solutions. They iteratively improve the solution while occasionally considering less favorable configurations to avoid being confined to suboptimal areas. By guiding the search process intelligently, metaheuristics adapt dynamically and effectively solve the TSP, often producing near-optimal solutions even for large-scale or complex problem instances.

	==Popular ~~Heuristic~~ Algorithms==		== Popular Optimization Heuristics Algorithms ==

	=== '''Heuristic Algorithms''' ===		=== '''Heuristic Algorithms''' ===