import random import math import copy Define the standard QWERTY layout with…
- User
import random import math import copy
Define the standard QWERTY layout with coordinates, including space
STANDARD_QWERTY = [ ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'], ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'], ['z', 'x', 'c', 'v', 'b', 'n', 'm'], [' '] # Space bar in a separate row ]
Create a list of positions based on the standard layout
def get_position_list(layout): positions = [] for row_idx, row in enumerate(layout): for col_idx, key in enumerate(row): positions.append((col_idx, row_idx)) return positions
POSITION_COORDS = get_position_list(STANDARD_QWERTY)
Define parameters for the genetic algorithm
POPULATION_SIZE = 200 # Increased population size for better diversity GENERATIONS = 1000 MUTATION_RATE = 0.2 # Increased mutation rate for more exploration TOURNAMENT_SIZE = 5 ELITISM_COUNT = 5 # Number of top individuals to carry over to the next generation
Function to calculate Euclidean distance between two positions
def distance(pos1, pos2): x1, y1 = pos1 x2, y2 = pos2 return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
Fitness function: lower total distance is better
def fitness(layout, text, position_coords): total_distance = 0 # Map each key to its position based on the layout key_to_pos = {key: position_coords[idx] for idx, key in enumerate(layout)}
for i in range(len(text) - 1): key1 = text[i] key2 = text[i + 1] if key1 in key_to_pos and key2 in key_to_pos: pos1 = key_to_pos[key1] pos2 = key_to_pos[key2] total_distance += distance(pos1, pos2) else: # Assign a large penalty if key not in layout total_distance += 100 return total_distanceInitialize population with random layouts
def initialize_population(characters, population_size): population = [] for _ in range(population_size): individual = characters[:] random.shuffle(individual) population.append(individual) return population
Selection: Tournament Selection with Elitism
def selection(population, fitnesses, tournament_size, elitism_count): # Sort population based on fitness sorted_population = [x for _, x in sorted(zip(fitnesses, population), key=lambda pair: pair[0])] # Elitism: carry the top individuals to the next generation elites = sorted_population[:elitism_count] selected = elites.copy() # Tournament selection for the rest while len(selected) < len(population): tournament = random.sample(list(zip(population, fitnesses)), tournament_size) tournament = sorted(tournament, key=lambda x: x[1]) winner = copy.deepcopy(tournament[0][0]) selected.append(winner) return selected
Crossover: Partially Mapped Crossover (PMX) for better genetic diversity
def crossover(parent1, parent2): size = len(parent1) child1, child2 = [None]*size, [None]*size
# Choose crossover points pt1, pt2 = sorted(random.sample(range(size), 2)) # Create offspring by copying the slice from parents child1[pt1:pt2] = parent1[pt1:pt2] child2[pt1:pt2] = parent2[pt1:pt2] def fill_child(child, parent_other): for gene in parent_other[pt1:pt2]: if gene not in child: pos = parent_other.index(gene) while child[pos] is not None: pos = parent_other.index(child[pos]) child[pos] = gene # Fill remaining positions with genes from parent_other for gene in parent_other: if gene not in child: for i in range(size): if child[i] is None: child[i] = gene break return child child1 = fill_child(child1, parent2) child2 = fill_child(child2, parent1) return child1, child2Mutation: Swap two keys
def mutate(individual, mutation_rate): for i in range(len(individual)): if random.random() < mutation_rate: j = random.randint(0, len(individual) - 1) individual[i], individual[j] = individual[j], individual[i] return individual
Genetic Algorithm
def genetic_algorithm(text, position_coords, population_size, generations, mutation_rate, tournament_size, elitism_count): # Sanitize and prepare the characters to include in the keyboard text = text.lower() valid_chars = set('abcdefghijklmnopqrstuvwxyz ') sanitized_text = ''.join([c for c in text if c in valid_chars]) characters = list(set(sanitized_text)) if ' ' in sanitized_text and ' ' not in characters: characters.append(' ') # Ensure we have exactly the required number of keys, pad if necessary required_keys = len(position_coords) # 27 positions (a-z and space) if len(characters) < required_keys: # Add random characters to fill while len(characters) < required_keys: char = random.choice('abcdefghijklmnopqrstuvwxyz ') if char not in characters: characters.append(char) elif len(characters) > required_keys: # Truncate to required keys characters = characters[:required_keys]
# Initialize population population = initialize_population(characters, population_size) best_layout = None best_fitness = float('inf') for gen in range(1, generations + 1): # Evaluate fitness fitnesses = [fitness(ind, sanitized_text, position_coords) for ind in population] # Find the best in current population min_fitness = min(fitnesses) if min_fitness < best_fitness: best_fitness = min_fitness best_layout = population[fitnesses.index(min_fitness)] print(f"Generation {gen}: Best Fitness = {best_fitness}") # Early stopping if perfect fitness is achieved if best_fitness == 0: print("Perfect layout found!") break # Selection with Elitism selected = selection(population, fitnesses, tournament_size, elitism_count) # Crossover to produce offspring offspring = [] for i in range(0, population_size - elitism_count, 2): parent1 = selected[i] parent2 = selected[i + 1] if i + 1 < population_size - elitism_count else selected[0] child1, child2 = crossover(parent1, parent2) offspring.extend([child1, child2]) # Add elites to the offspring offspring.extend(selected[:elitism_count]) # Mutation population = [mutate(child, mutation_rate) for child in offspring] return best_layout, best_fitnessExample usage
if name == "main": # Example text text = "hello world this is an example text to optimize the keyboard layout using genetic algorithm and the quick brown fox jumps over the lazy dog"
# Get position coordinates based on the standard layout position_coords = POSITION_COORDS # Run genetic algorithm best_layout, best_fitness = genetic_algorithm( text=text, position_coords=position_coords, population_size=200, # Increased population size for better diversity generations=1000, mutation_rate=0.2, # Increased mutation rate for more exploration tournament_size=5, elitism_count=5 ) # Define row lengths for visualization, including the space bar row_lengths = [10, 9, 7, 1] # Adjusted to include the space print("\nBest Keyboard Layout:") # Arrange the best layout back to QWERTY rows output_layout = [] idx = 0 for length in row_lengths: row = best_layout[idx:idx + length] output_layout.append(row) idx += length for row in output_layout: print(' '.join(row)) print(f"\nBest Fitness (Total Distance): {best_fitness}") // 이 코드가 하는 일이 뭔지 설명해봐. - Assistant
이 코드는 주어진 텍스트를 입력할 때 키보드에서의 키 이동 거리를 최소화하기 위해 키보드 레이아웃을 최적화하는 **유전 알고리즘(Genetic Algorithm)**을 구현한 것입니다. 구체적으로, 표준 QWERTY 키보드 레이아웃을 기반으로 하여 키들의 위치를 변경함으로써 전체 타이핑 시 이동 거리를 줄이는 것을 목표로 합니다. 아래에서 코드의 각 부분과 전체적인 동작 방식을 상세히 설명하겠습니다.
주요 구성 요소 및 기능
-
라이브러리 임포트
import random import math import copyrandom: 랜덤한 수 생성 및 샘플링에 사용.math: 수학적 계산, 특히 유클리드 거리 계산에 사용.copy: 객체의 깊은 복사(deep copy)에 사용.
-
표준 QWERTY 레이아웃 정의
STANDARD_QWERTY = [ ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'], ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'], ['z', 'x', 'c', 'v', 'b', 'n', 'm'], [' '] # Space bar in a separate row ]- 표준 QWERTY 키보드 배열을 행(row)별로 리스트로 정의.
- 마지막 행에는 스페이스 바(공백 문자)를 별도로 포함.
-
키의 위치 좌표 생성
def get_position_list(layout): positions = [] for row_idx, row in enumerate(layout): for col_idx, key in enumerate(row): positions.append((col_idx, row_idx)) return positions POSITION_COORDS = get_position_list(STANDARD_QWERTY)- 각 키의 좌표를
(열, 행)형태로 리스트에 저장. - 예를 들어, 'q'는
(0,0), 'w'는(1,0), ..., 스페이스는(0,3)과 같은 방식.
- 각 키의 좌표를
-
유전 알고리즘 파라미터 설정
POPULATION_SIZE = 200 # 인구 집단의 크기 GENERATIONS = 1000 # 세대 수 MUTATION_RATE = 0.2 # 돌연변이 확률 TOURNAMENT_SIZE = 5 # 토너먼트 선택 시 참가 인원 ELITISM_COUNT = 5 # 엘리트(상위) 개체 수- 인구 집단 크기: 동시에 유지되는 레이아웃 후보의 수.
- 세대 수: 알고리즘이 반복되는 횟수.
- 돌연변이 확률: 각 유전자(키)의 돌연변이가 발생할 확률.
- 토너먼트 크기: 선택 단계에서 경쟁하는 후보 수.
- 엘리티즘: 최상의 개체를 다음 세대로 직접 전달하는 수.
-
유클리드 거리 계산 함수
def distance(pos1, pos2): x1, y1 = pos1 x2, y2 = pos2 return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)- 두 키 사이의 거리 계산.
-
적합도 함수 정의
def fitness(layout, text, position_coords): total_distance = 0 # Map each key to its position based on the layout key_to_pos = {key: position_coords[idx] for idx, key in enumerate(layout)} for i in range(len(text) - 1): key1 = text[i] key2 = text[i + 1] if key1 in key_to_pos and key2 in key_to_pos: pos1 = key_to_pos[key1] pos2 = key_to_pos[key2] total_distance += distance(pos1, pos2) else: # Assign a large penalty if key not in layout total_distance += 100 return total_distance- 적합도(Fitness): 전체 텍스트를 입력할 때 발생하는 키 이동 거리의 합.
- 레이아웃에 존재하지 않는 키가 있을 경우 큰 페널티(100)를 추가.
- 적합도 값이 낮을수록 레이아웃이 더 좋음.
-
초기 인구 집단 생성
def initialize_population(characters, population_size): population = [] for _ in range(population_size): individual = characters[:] random.shuffle(individual) population.append(individual) return population- 주어진 문자 집합(
characters)을 무작위로 섞어 여러 레이아웃 후보를 생성.
- 주어진 문자 집합(
-
선택 연산: 토너먼트 선택과 엘리티즘
def selection(population, fitnesses, tournament_size, elitism_count): # Sort population based on fitness sorted_population = [x for _, x in sorted(zip(fitnesses, population), key=lambda pair: pair[0])] # Elitism: carry the top individuals to the next generation elites = sorted_population[:elitism_count] selected = elites.copy() # Tournament selection for the rest while len(selected) < len(population): tournament = random.sample(list(zip(population, fitnesses)), tournament_size) tournament = sorted(tournament, key=lambda x: x[1]) winner = copy.deepcopy(tournament[0][0]) selected.append(winner) return selected- 엘리트 선택: 가장 적합한 상위
elitism_count개체를 다음 세대로 직접 전달. - 토너먼트 선택: 무작위로 선택된
tournament_size개체 중 가장 적합한 개체를 선택하여 나머지 인구를 구성.
- 엘리트 선택: 가장 적합한 상위
-
교차 연산: 부분 매핑 교차(PMX)
def crossover(parent1, parent2): size = len(parent1) child1, child2 = [None]*size, [None]*size # Choose crossover points pt1, pt2 = sorted(random.sample(range(size), 2)) # Create offspring by copying the slice from parents child1[pt1:pt2] = parent1[pt1:pt2] child2[pt1:pt2] = parent2[pt1:pt2] def fill_child(child, parent_other): for gene in parent_other[pt1:pt2]: if gene not in child: pos = parent_other.index(gene) while child[pos] is not None: pos = parent_other.index(child[pos]) child[pos] = gene # Fill remaining positions with genes from parent_other for gene in parent_other: if gene not in child: for i in range(size): if child[i] is None: child[i] = gene break return child child1 = fill_child(child1, parent2) child2 = fill_child(child2, parent1) return child1, child2- 부분 매핑 교차(PMX): 두 부모의 일정 범위 내 유전자(키)를 교환하여 자식 개체를 생성.
- 교차 지점(
pt1,pt2) 사이의 유전자를 복사하고, 나머지 유전자는 부모의 유전자를 기반으로 채움. - 이 방법은 유전자 중복을 방지하고 다양한 조합을 생성하는 데 효과적.
-
돌연변이 연산: 두 키 교환
def mutate(individual, mutation_rate): for i in range(len(individual)): if random.random() < mutation_rate: j = random.randint(0, len(individual) - 1) individual[i], individual[j] = individual[j], individual[i] return individual- 각 유전자(키)에 대해
mutation_rate확률로 다른 임의의 키와 교환. - 레이아웃의 다양성을 유지하고 새로운 해를 탐색하는 데 도움.
- 각 유전자(키)에 대해
-
유전 알고리즘 메인 함수
def genetic_algorithm(text, position_coords, population_size, generations, mutation_rate, tournament_size, elitism_count): # Sanitize and prepare the characters to include in the keyboard text = text.lower() valid_chars = set('abcdefghijklmnopqrstuvwxyz ') sanitized_text = ''.join([c for c in text if c in valid_chars]) characters = list(set(sanitized_text)) if ' ' in sanitized_text and ' ' not in characters: characters.append(' ') # Ensure we have exactly the required number of keys, pad if necessary required_keys = len(position_coords) # 27 positions (a-z and space) if len(characters) < required_keys: # Add random characters to fill while len(characters) < required_keys: char = random.choice('abcdefghijklmnopqrstuvwxyz ') if char not in characters: characters.append(char) elif len(characters) > required_keys: # Truncate to required keys characters = characters[:required_keys] # Initialize population population = initialize_population(characters, population_size) best_layout = None best_fitness = float('inf') for gen in range(1, generations + 1): # Evaluate fitness fitnesses = [fitness(ind, sanitized_text, position_coords) for ind in population] # Find the best in current population min_fitness = min(fitnesses) if min_fitness < best_fitness: best_fitness = min_fitness best_layout = population[fitnesses.index(min_fitness)] print(f"Generation {gen}: Best Fitness = {best_fitness}") # Early stopping if perfect fitness is achieved if best_fitness == 0: print("Perfect layout found!") break # Selection with Elitism selected = selection(population, fitnesses, tournament_size, elitism_count) # Crossover to produce offspring offspring = [] for i in range(0, population_size - elitism_count, 2): parent1 = selected[i] parent2 = selected[i + 1] if i + 1 < population_size - elitism_count else selected[0] child1, child2 = crossover(parent1, parent2) offspring.extend([child1, child2]) # Add elites to the offspring offspring.extend(selected[:elitism_count]) # Mutation population = [mutate(child, mutation_rate) for child in offspring] return best_layout, best_fitness- 입력 텍스트 전처리: 소문자 변환 및 유효한 문자(알파벳 소문자와 공백)만 남김.
- 문자 집합 준비: 텍스트에 사용된 고유 문자를 추출하고, 필요한 경우 랜덤하게 추가 또는 잘라냄으로써 키보드의 모든 위치에 문자를 배치 가능하게 함.
- 초기 인구 집단 생성:
initialize_population함수를 통해 초기 레이아웃 후보군을 생성. - 세대 반복:
- 적합도 평가: 각 개체의 적합도를 계산.
- 최적 개체 갱신: 현재 세대에서 가장 적합한 개체를 저장.
- 조기 종료 조건: 적합도가 0인 완벽한 레이아웃이 발견되면 알고리즘 종료.
- 선택:
selection함수를 통해 다음 세대 후보를 선택. - 교차: 선택된 개체들 간에 교배를 통해 자식 개체 생성.
- 엘리트 추가: 상위 엘리트를 자손에 추가.
- 돌연변이: 자손 개체에 돌연변이를 적용.
- 최종 결과 반환: 가장 적합한 레이아웃과 그 적합도 반환.
-
메인 블록: 알고리즘 실행 및 결과 출력
if __name__ == "__main__": # Example text text = "hello world this is an example text to optimize the keyboard layout using genetic algorithm and the quick brown fox jumps over the lazy dog" # Get position coordinates based on the standard layout position_coords = POSITION_COORDS # Run genetic algorithm best_layout, best_fitness = genetic_algorithm( text=text, position_coords=position_coords, population_size=200, # Increased population size for better diversity generations=1000, mutation_rate=0.2, # Increased mutation rate for more exploration tournament_size=5, elitism_count=5 ) # Define row lengths for visualization, including the space bar row_lengths = [10, 9, 7, 1] # Adjusted to include the space print("\nBest Keyboard Layout:") # Arrange the best layout back to QWERTY rows output_layout = [] idx = 0 for length in row_lengths: row = best_layout[idx:idx + length] output_layout.append(row) idx += length for row in output_layout: print(' '.join(row)) print(f"\nBest Fitness (Total Distance): {best_fitness}")- 입력 텍스트: 알고리즘이 최적화를 시도할 텍스트. 이 예에서는 "hello world this is an example text..."와 같은 긴 문장.
- 유전 알고리즘 실행: 앞서 정의한
genetic_algorithm함수를 호출하여 최적의 키보드 레이아웃과 그 적합도를 얻음. - 결과 출력 준비:
- 최적 레이아웃을 표준 QWERTY 레이아웃과 동일한 행 구조로 재배치.
- 각 행의 길이를
[10, 9, 7, 1]로 정의 (스페이스 바를 별도로 고려).
- 최적 레이아웃 출력:
- 최적 레이아웃을 행별로 출력하여 보기 쉽게 표시.
- 전체 거리 합(
Best Fitness)을 출력.
동작 과정 요약
-
초기화: 주어진 텍스트에서 사용된 고유 문자를 추출하고, 필요 시 추가 문자를 통해 전체 키보드 위치에 문자를 배치할 수 있도록 준비합니다.
-
초기 인구 생성: 랜덤하게 섞인 문자 배열을 통해 초기 레이아웃 후보군을 생성합니다.
-
적합도 평가: 각 레이아웃 별로, 주어진 텍스트를 입력할 때 발생하는 키 이동 거리의 총합을 계산합니다.
-
선택 및 교배:
- 상위 엘리트와 토너먼트 선택을 통해 다음 세대를 위한 부모를 선택합니다.
- 선택된 부모들 간에 교차 연산을 통해 새로운 자식 레이아웃을 생성합니다.
-
돌연변이: 자식 레이아웃에 대해 일정 확률로 돌연변이를 적용하여 레이아웃의 다양성을 유지하고 새로운 해를 탐색합니다.
-
반복: 지정된 세대 수만큼 또는 완벽한 레이아웃(적합도 0)이 발견될 때까지 위 과정을 반복합니다.
-
결과 출력: 가장 적합한 레이아웃을 시각적으로 출력하고, 그 적합도(총 거리)를 표시합니다.
코드의 목표 및 활용 방안
이 코드는 키보드 레이아웃을 사용자에게 최적화하여 타이핑 효율성을 향상시키는 데 활용될 수 있습니다. 예를 들어, 특정 사용자가 주로 사용하는 텍스트에 맞춰 키보드 레이아웃을 맞춤 설정함으로써, 손의 이동 거리를 줄이고 타이핑 속도나 정확성을 향상시킬 수 있습니다. 또한, 일반적인 타이핑 패턴을 분석하여 다양한 사용자 맞춤형 키보드 레이아웃을 생성하는 데에도 응용될 수 있습니다.
추가 개선 및 고려 사항
-
더 복잡한 적합도 함수:
- 현재는 연속된 두 키 간의 거리 합을 기반으로 하지만, 자주 사용하는 키의 비율이나 손의 피로도 등을 고려할 수 있습니다.
-
병렬 처리:
- 인구 집단이 클 경우 계산 시간이 길어질 수 있으므로, 병렬 처리를 통해 성능을 향상시킬 수 있습니다.
-
다양한 교차 및 돌연변이 기법 시험:
- 다른 교차(Crossover) 및 돌연변이(Mutation) 기법을 실험하여 알고리즘의 효율성을 높일 수 있습니다.
-
사용자 인터페이스:
- 최적화된 레이아웃을 시각적으로 표시하거나, 실제 키보드 설정으로 쉽게 변환할 수 있는 인터페이스를 제공할 수 있습니다.
-
다양한 텍스트 데이터 사용:
- 특정 사용자나 특정 용도에 맞는 다양한 텍스트 데이터를 사용하여, 보다 맞춤형 레이아웃을 생성할 수 있습니다.
이 코드는 유전 알고리즘의 기본 개념을 활용하여 키보드 레이아웃 최적화 문제를 효과적으로 해결하려는 시도로 볼 수 있습니다. 다양한 최적화 기법과 파라미터 조정을 통해 성능을 더욱 향상시킬 수 있으며, 사용자 맞춤형 키보드 레이아웃 설계에 응용할 수 있는 유용한 도구입니다.
-