{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.10.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"none","dataSources":[{"sourceId":88046,"databundleVersionId":10229277,"sourceType":"competition"},{"sourceId":10454976,"sourceType":"datasetVersion","datasetId":6346030},{"sourceId":104492,"sourceType":"modelInstanceVersion","isSourceIdPinned":true,"modelInstanceId":72255,"modelId":76277}],"dockerImageVersionId":30827,"isInternetEnabled":true,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"code","source":"pip install transformers==4.45.1","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-01-14T04:30:49.534481Z","iopub.execute_input":"2025-01-14T04:30:49.534907Z","iopub.status.idle":"2025-01-14T04:31:07.791185Z","shell.execute_reply.started":"2025-01-14T04:30:49.534870Z","shell.execute_reply":"2025-01-14T04:31:07.790049Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import gc\nimport os\nfrom math import exp\nfrom collections import Counter\nfrom typing import List, Optional, Union\nimport pickle\nimport numpy as np\nimport pandas as pd\nimport transformers\nimport torch\n\nos.environ['OMP_NUM_THREADS'] = '1'\nos.environ['TOKENIZERS_PARALLELISM'] = 'false'\nPAD_TOKEN_LABEL_ID = torch.nn.CrossEntropyLoss().ignore_index\nDEVICE = torch.device('cuda' if torch.cuda.is_available() else 'cpu')\n\n\nclass ParticipantVisibleError(Exception):\n    pass\n\n\ndef score(\n    solution: pd.DataFrame,\n    submission: pd.DataFrame,\n    row_id_column_name: str,\n    model_path: str = '/kaggle/input/gemma-2/transformers/gemma-2-9b/2',\n    load_in_8bit: bool = True,\n    clear_mem: bool = False,\n) -> float:\n    \"\"\"\n    Calculates the mean perplexity of submitted text permutations compared to an original text.\n\n    Parameters\n    ----------\n    solution : DataFrame\n        DataFrame containing the original text in a column named 'text'.\n        Includes a row ID column specified by `row_id_column_name`.\n\n    submission : DataFrame\n        DataFrame containing the permuted text in a column named 'text'.\n        Must have the same row IDs as the solution.\n        Includes a row ID column specified by `row_id_column_name`.\n\n    row_id_column_name : str\n        Name of the column containing row IDs.\n        Ensures aligned comparison between solution and submission.\n\n    model_path : str\n        Path to the serialized LLM.\n\n    clear_mem : bool\n        Clear GPU memory after scoring by clearing the CUDA cache.\n        Useful for testing.\n\n    Returns\n    -------\n    float\n        The mean perplexity score. Lower is better.\n\n    Raises\n    ------\n    ParticipantVisibleError\n        If the submission format is invalid or submitted strings are not valid permutations.\n\n    Examples\n    --------\n    >>> import pandas as pd\n    >>> model_path = \"/kaggle/input/gemma-2/transformers/gemma-2-9b/2\"\n    >>> solution = pd.DataFrame({\n    ...     'id': [0, 1],\n    ...     'text': [\"this is a normal english sentence\", \"the quick brown fox jumps over the lazy dog\"]\n    ... })\n    >>> submission = pd.DataFrame({\n    ...     'id': [0, 1],\n    ...     'text': [\"sentence english normal a is this\", \"lazy the over jumps fox brown quick the dog\"]\n    ... })\n    >>> score(solution, submission, 'id', model_path=model_path, clear_mem=True) > 0\n    True\n    \"\"\"\n    # Check that each submitted string is a permutation of the solution string\n    sol_counts = solution.loc[:, 'text'].str.split().apply(Counter)\n    sub_counts = submission.loc[:, 'text'].str.split().apply(Counter)\n    invalid_mask = sol_counts != sub_counts\n    if invalid_mask.any():\n        raise ParticipantVisibleError(\n            'At least one submitted string is not a valid permutation of the solution string.'\n        )\n\n    # Calculate perplexity for the submitted strings\n    sub_strings = [\n        ' '.join(s.split()) for s in submission['text'].tolist()\n    ]  # Split and rejoin to normalize whitespace\n    scorer = PerplexityCalculator(\n        model_path=model_path,\n        load_in_8bit=load_in_8bit,\n    )  # Initialize the perplexity calculator with a pre-trained model\n    perplexities = scorer.get_perplexity(\n        sub_strings\n    )  # Calculate perplexity for each submitted string\n\n    if clear_mem:\n        # Just move on if it fails. Not essential if we have the score.\n        try:\n            scorer.clear_gpu_memory()\n        except:\n            print('GPU memory clearing failed.')\n\n    return float(np.mean(perplexities))\n\n\nclass PerplexityCalculator:\n    \"\"\"\n    Calculates perplexity of text using a pre-trained language model.\n\n    Adapted from https://github.com/asahi417/lmppl/blob/main/lmppl/ppl_recurrent_lm.py\n\n    Parameters\n    ----------\n    model_path : str\n        Path to the pre-trained language model\n\n    load_in_8bit : bool, default=False\n        Use 8-bit quantization for the model. Requires CUDA.\n\n    device_map : str, default=\"auto\"\n        Device mapping for the model.\n    \"\"\"\n\n    def __init__(\n        self,\n        model_path: str,\n        load_in_8bit: bool = False,\n        device_map: str = 'auto',\n    ):\n        self.tokenizer = transformers.AutoTokenizer.from_pretrained(model_path,padding_side=\"right\")\n        # Configure model loading based on quantization setting and device availability\n        if load_in_8bit:\n            if DEVICE.type != 'cuda':\n                raise ValueError('8-bit quantization requires CUDA device')\n                \n            #quantization_config = transformers.BitsAndBytesConfig(load_in_8bit=True)\n            #quantization_config = transformers.BitsAndBytesConfig(load_in_4bit=True)\n\n            quantization_config = transformers.BitsAndBytesConfig(\n                load_in_4bit = True,\n                bnb_4bit_quant_type = \"fp4\", #fp4 nf4\n                bnb_4bit_use_double_quant = False,\n                bnb_4bit_compute_dtype=torch.float16,\n            )\n            \n            self.model = transformers.AutoModelForCausalLM.from_pretrained(\n                model_path,\n                quantization_config=quantization_config,\n                device_map=device_map,\n            )\n        else:\n            self.model = transformers.AutoModelForCausalLM.from_pretrained(\n                model_path,\n                torch_dtype=torch.float16 if DEVICE.type == 'cuda' else torch.float32,\n                device_map=device_map,\n            )\n\n        self.loss_fct = torch.nn.CrossEntropyLoss(reduction='none')\n\n        self.model.eval()\n        #if not load_in_8bit:\n        #    self.model.to(DEVICE)  # Explicitly move the model to the device\n\n    def get_perplexity(\n        self, input_texts: Union[str, List[str]], batch_size: 32\n    ) -> Union[float, List[float]]:\n        \"\"\"\n        Calculates the perplexity of given texts.\n\n        Parameters\n        ----------\n        input_texts : str or list of str\n            A single string or a list of strings.\n\n        batch_size : int, default=None\n            Batch size for processing. Defaults to the number of input texts.\n\n        verbose : bool, default=False\n            Display progress bar.\n\n        Returns\n        -------\n        float or list of float\n            A single perplexity value if input is a single string,\n            or a list of perplexity values if input is a list of strings.\n\n        Examples\n        --------\n        >>> import pandas as pd\n        >>> model_path = \"/kaggle/input/gemma-2/transformers/gemma-2-9b/2\"\n        >>> scorer = PerplexityCalculator(model_path=model_path)\n\n        >>> submission = pd.DataFrame({\n        ...     'id': [0, 1, 2],\n        ...     'text': [\"this is a normal english sentence\", \"thsi is a slihgtly misspelled zr4g sentense\", \"the quick brown fox jumps over the lazy dog\"]\n        ... })\n        >>> perplexities = scorer.get_perplexity(submission[\"text\"].tolist())\n        >>> perplexities[0] < perplexities[1]\n        True\n        >>> perplexities[2] < perplexities[0]\n        True\n\n        >>> perplexities = scorer.get_perplexity([\"this is a sentence\", \"another sentence\"])\n        >>> all(p > 0 for p in perplexities)\n        True\n\n        >>> scorer.clear_gpu_memory()\n        \"\"\"\n        single_input = isinstance(input_texts, str)\n        input_texts = [input_texts] if single_input else input_texts\n\n        loss_list = []\n\n        batches = len(input_texts)//batch_size + (len(input_texts)%batch_size != 0)\n        for j in range(batches):\n            \n            a = j*batch_size\n            b = (j+1)*batch_size\n            input_batch = input_texts[a:b]\n        \n            with torch.no_grad():\n\n                # Explicitly add sequence boundary tokens to the text\n                text_with_special = [f\"{self.tokenizer.bos_token}{text}{self.tokenizer.eos_token}\" for text in input_batch]\n\n                # Tokenize\n                model_inputs = self.tokenizer(\n                    text_with_special,\n                    return_tensors='pt',\n                    add_special_tokens=False,\n                    padding=True\n                )\n\n                if 'token_type_ids' in model_inputs:\n                    model_inputs.pop('token_type_ids')\n\n                model_inputs = {k: v.to(DEVICE) for k, v in model_inputs.items()}\n\n                # Get model output\n                output = self.model(**model_inputs, use_cache=False)\n                logits = output['logits']\n\n                label = model_inputs['input_ids']\n                label[label == self.tokenizer.pad_token_id] = PAD_TOKEN_LABEL_ID\n\n                # Shift logits and labels for calculating loss\n                shift_logits = logits[..., :-1, :].contiguous()  # Drop last prediction\n                shift_labels = label[..., 1:].contiguous()  # Drop first input\n\n                # Calculate token-wise loss\n                loss = self.loss_fct(\n                    shift_logits.view(-1, shift_logits.size(-1)),\n                    shift_labels.view(-1)\n                )\n\n                loss = loss.view(len(logits), -1)\n                valid_length = (shift_labels != PAD_TOKEN_LABEL_ID).sum(dim=-1)\n                loss = torch.sum(loss, -1) / valid_length\n\n                loss_list += loss.cpu().tolist()\n\n                # Debug output\n                #print(f\"\\nProcessing: '{text}'\")\n                #print(f\"With special tokens: '{text_with_special}'\")\n                #print(f\"Input tokens: {model_inputs['input_ids'][0].tolist()}\")\n                #print(f\"Target tokens: {shift_labels[0].tolist()}\")\n                #print(f\"Input decoded: {self.tokenizer.decode(model_inputs['input_ids'][0])}\")\n                #print(f\"Target decoded: {self.tokenizer.decode(shift_labels[0])}\")\n                #print(f\"Individual losses: {loss.tolist()}\")\n                #print(f\"Average loss: {sequence_loss.item():.4f}\")\n\n        ppl = [exp(i) for i in loss_list]\n\n        # print(\"\\nFinal perplexities:\")\n        # for text, perp in zip(input_texts, ppl):\n        #     print(f\"Text: '{text}'\")\n        #     print(f\"Perplexity: {perp:.2f}\")\n\n        return ppl[0] if single_input else ppl\n\n    def clear_gpu_memory(self) -> None:\n        \"\"\"Clears GPU memory by deleting references and emptying caches.\"\"\"\n        if not torch.cuda.is_available():\n            return\n\n        # Delete model and tokenizer if they exist\n        if hasattr(self, 'model'):\n            del self.model\n        if hasattr(self, 'tokenizer'):\n            del self.tokenizer\n\n        # Run garbage collection\n        gc.collect()\n\n        # Clear CUDA cache and reset memory stats\n        with DEVICE:\n            torch.cuda.empty_cache()\n            torch.cuda.ipc_collect()\n            torch.cuda.reset_peak_memory_stats()\n\n# LOAD GEMMA SCORER\nscorer = PerplexityCalculator('/kaggle/input/gemma-2/transformers/gemma-2-9b/2')\n\npast = {}\n# You can comment out the following lines to run on a faster GPU with different scoring\nwith open('/kaggle/input/santa-2024-perplexity-permutation-puzzle-scores/past.pickle', 'rb') as handle:\n    past = pickle.load(handle)\nprint(len(past))\n\n\nimport re, sys\n\nclass Reprinter:\n    def __init__(self):\n        self.text = ''\n\n    def moveup(self, lines):\n        for _ in range(lines):\n            sys.stdout.write(\"\\x1b[A\")\n\n    def reprint(self, text):\n        # Clear previous text by overwritig non-spaces with spaces\n        self.moveup(self.text.count(\"\\n\"))\n        sys.stdout.write(re.sub(r\"[^\\s]\", \" \", self.text))\n\n        # Print new text\n        lines = min(self.text.count(\"\\n\"), text.count(\"\\n\"))\n        self.moveup(lines)\n        sys.stdout.write(text)\n        self.text = text\n\nreprinter = Reprinter()","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"execution":{"iopub.status.busy":"2025-01-14T04:31:21.440519Z","iopub.execute_input":"2025-01-14T04:31:21.440891Z","iopub.status.idle":"2025-01-14T04:31:29.046480Z","shell.execute_reply.started":"2025-01-14T04:31:21.440858Z","shell.execute_reply":"2025-01-14T04:31:29.045226Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"words_0 = [\n    'reindeer', 'mistletoe', 'elf', 'gingerbread', 'family', 'advent', 'scrooge', 'chimney', \n    'fireplace', 'ornament'\n]\nwords_1 = [\n    'reindeer', 'sleep', 'walk', 'the', 'night', 'and', 'drive', 'mistletoe', 'scrooge', 'laugh', \n    'chimney', 'jump', 'elf', 'bake', 'gingerbread', 'family', 'give', 'advent', 'fireplace', \n    'ornament'\n]\nwords_2 = [\n    'sleigh', 'yuletide', 'beard', 'carol', 'cheer', 'chimney', 'decorations', 'gifts', 'grinch', \n    'holiday', 'holly', 'jingle', 'magi', 'naughty', 'nice', 'nutcracker', 'ornament', 'polar', \n    'workshop', 'stocking'\n]\nwords_3 = [\n    'sleigh', 'of', 'the', 'magi', 'yuletide', 'cheer', 'is', 'unwrap', 'gifts', 'and', 'eat', \n    'cheer', 'holiday', 'decorations', 'holly', 'jingle', 'relax', 'sing', 'carol', 'visit', \n    'workshop', 'grinch', 'naughty', 'nice', 'chimney', 'stocking', 'ornament', 'nutcracker', \n    'polar', 'beard'\n]\nwords_4 = [\n    'from', 'and', 'of', 'to', 'the', 'as', 'in', 'that', 'it', 'we', 'with', 'not', 'you', \n    'have', 'milk', 'chocolate', 'candy', 'peppermint', 'eggnog', 'cookie', 'fruitcake', 'toy', \n    'doll', 'game', 'puzzle', 'greeting', 'card', 'wrapping', 'paper', 'bow', 'wreath', 'poinsettia', \n    'snowglobe', 'candle', 'fireplace', 'wish', 'dream', 'hope', 'believe', 'wonder', 'night', \n    'star', 'angel', 'peace', 'joy', 'season', 'merry', 'hohoho', 'kaggle', 'workshop'\n]\nwords_5 = [\n    'from', 'and', 'and', 'as', 'we', 'and', 'have', 'the', 'in', 'is', 'it', 'of', 'not', \n    'that', 'the', 'to', 'with', 'you', 'advent', 'card', 'angel', 'bake', 'beard', 'believe', \n    'bow', 'candy', 'candle', 'carol', 'cheer', 'cheer', 'chocolate', 'chimney', 'cookie', \n    'decorations', 'doll', 'dream', 'drive', 'eat', 'eggnog', 'family', 'fireplace', 'fireplace', \n    'chimney', 'fruitcake', 'game', 'gifts', 'give', 'gingerbread', 'greeting', 'grinch', 'holiday', \n    'holly', 'hohoho', 'hope', 'jingle', 'jump', 'joy', 'kaggle', 'laugh', 'magi', 'merry', 'milk', \n    'mistletoe', 'naughty', 'nice', 'night', 'night', 'elf', 'nutcracker', 'ornament', 'ornament', \n    'of', 'the', 'wrapping', 'paper', 'peace', 'peppermint', 'polar', 'poinsettia', 'puzzle', \n    'reindeer', 'relax', 'scrooge', 'season', 'sing', 'sleigh', 'sleep', 'snowglobe', 'star', 'stocking', \n    'toy', 'unwrap', 'visit', 'walk', 'wish', 'wonder', 'workshop', 'workshop', 'wreath', 'yuletide'\n]\n\n\n\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-01-14T04:31:32.183314Z","iopub.execute_input":"2025-01-14T04:31:32.183722Z","iopub.status.idle":"2025-01-14T04:31:32.192879Z","shell.execute_reply.started":"2025-01-14T04:31:32.183686Z","shell.execute_reply":"2025-01-14T04:31:32.191767Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import json\nimport random\nimport pandas as pd\nimport time\n\n# Assuming `score` function and PerplexityCalculator (scorer) are already available\niteration = 0\n\nstart_time = time.time()\nimport math\n\ndef simulated_annealing_v4(text: str, temp_start=6.0, temp_end=1.0, cooling_rate=0.2,\n                           n_neighbor=2, steps_per_temp=4, verbose=False, seq_to_choose=None,\n                           factor_acceptance=1.0):\n    import math\n    import random\n    \n    words = text.split()\n    current = words[:]\n    current_score = scorer.get_perplexity(' '.join(current), batch_size=BATCH_SIZE)\n    max_retries = 10\n    retries = 0\n\n    while math.isnan(current_score) and retries < max_retries:\n        random.shuffle(current)\n        current_score = scorer.get_perplexity(' '.join(current), batch_size=BATCH_SIZE)\n        retries += 1\n    if math.isnan(current_score):\n        raise ValueError(\"Unable to compute a valid perplexity score after retries.\")\n\n    best = current[:]\n    best_score = current_score\n    temp = temp_start\n\n    seq_no_k = seq_to_choose if seq_to_choose is not None else list(range(len(words)))\n    iteration = 0\n\n    while temp > temp_end:\n        for _ in range(steps_per_temp):\n            if len(seq_no_k) < n_neighbor:\n                n_neighbor = len(seq_no_k)\n\n            indices = random.sample(seq_no_k, n_neighbor)\n            neighbor = current[:]\n            if n_neighbor == 2:\n                neighbor[indices[0]], neighbor[indices[1]] = neighbor[indices[1]], neighbor[indices[0]]\n            else:\n                continue  # Simplify for now, extend as needed for larger n_neighbor\n            \n            neighbor_score = scorer.get_perplexity(' '.join(neighbor), batch_size=BATCH_SIZE)\n            if math.isnan(neighbor_score):\n                continue\n\n            delta = neighbor_score - current_score\n            acceptance_prob = math.exp(-delta / (temp * factor_acceptance))\n            if delta < 0 or random.random() < acceptance_prob:\n                current, current_score = neighbor[:], neighbor_score\n                if current_score < best_score:\n                    best, best_score = current[:], current_score\n                    if verbose:\n                        print(f\"New best: {' '.join(best)} | Score: {best_score:.2f}\")\n\n        temp *= cooling_rate\n        iteration += 1\n        if verbose:\n            print(f\"Iteration {iteration}: Temp={temp:.2f}, Current Score={current_score:.2f}\")\n\n    return ' '.join(best), best_score\n\n\n# Genetic Algorithm Functions\ndef create_population(size, words):\n    \"\"\" Create an initial population of random permutations of the given words. \"\"\"\n    population = []\n    for _ in range(size):\n        random.shuffle(words)\n        population.append(words[:])  # make a copy of the shuffled list\n    return population\n\ndef calculate_fitness(population, solution_df, row_id_column_name):\n    \"\"\" Calculate the fitness of each individual (lower perplexity is better). \"\"\"\n    fitness_scores = []\n    for individual in population:\n        # Create a string for the permuted text\n        permuted_text = ' '.join(individual)\n        if permuted_text in past:\n            perplexity = past[permuted_text]\n        else:\n            perplexity = scorer.get_perplexity(permuted_text, 4)\n            past[permuted_text] = perplexity\n\n        # Calculate perplexity using the scorer (PerplexityCalculator)\n        perplexity = scorer.get_perplexity(permuted_text, 4)\n        fitness_scores.append(perplexity)  # lower perplexity is better\n        \n        # Optionally print iteration and perplexity (using reprinter)\n        global iteration\n        iteration += 1\n        reprinter.reprint(f\"Iteration: {iteration}, Perplexity: {perplexity:.2f}\\r\")\n\n    return fitness_scores\n\ndef tournament_selection(population, fitness_scores, num_parents, tournament_size=3):\n    selected_parents = []\n    for _ in range(num_parents):\n        # Tournament selection: pick a random sample of individuals and select the best one\n        tournament = random.sample(list(zip(population, fitness_scores)), tournament_size)\n        tournament.sort(key=lambda x: x[1])  # Sort by fitness (lower perplexity is better)\n        selected_parents.append(tournament[0][0])  # Select the best\n    return selected_parents\n    \ndef roulette_wheel_selection(population, fitness_scores, num_parents=2):\n    \"\"\" Perform roulette wheel selection to select parents. \"\"\"\n    total_fitness = sum(fitness_scores)\n    selection_probs = [1 - (score / total_fitness) for score in fitness_scores]  # Lower perplexity -> higher probability\n    selected_parents = random.choices(population, weights=selection_probs, k=num_parents)\n    return selected_parents\n\n\n\ndef elitism(population, fitness_scores, num_elites=2):\n    \"\"\" Select the best individuals (elites) to survive. \"\"\"\n    sorted_population = sorted(zip(population, fitness_scores), key=lambda x: x[1])\n    elites = [indiv[0] for indiv in sorted_population[:num_elites]]\n    return elites\n\n\ndef pmx_crossover(parent1, parent2, best_fitness, temperature, solution_df, row_id_column_name):\n    \"\"\" Perform Partially Matched Crossover (PMX) with acceptance of worse solutions. \"\"\"\n    size = len(parent1)\n    point1, point2 = sorted(random.sample(range(size), 2))  # Select two random crossover points\n\n    # Create offspring with the same structure as parents\n    offspring1 = [None] * size\n    offspring2 = [None] * size\n\n    # Copy the segments from parents\n    for i in range(point1, point2):\n        offspring1[i] = parent2[i]\n        offspring2[i] = parent1[i]\n\n    # Mapping to resolve duplicates\n    mapping1 = {parent2[i]: parent1[i] for i in range(point1, point2)}\n    mapping2 = {parent1[i]: parent2[i] for i in range(point1, point2)}\n\n    # Fill the remaining positions using the mapping\n    for i in range(size):\n        if offspring1[i] is None:\n            word = parent1[i]\n            while word in offspring1:  # Handle duplicates in offspring1\n                word = mapping1[word]\n            offspring1[i] = word\n\n        if offspring2[i] is None:\n            word = parent2[i]\n            while word in offspring2:  # Handle duplicates in offspring2\n                word = mapping2[word]\n            offspring2[i] = word\n\n    # Accept worse offspring with probability based on fitness difference and temperature\n    current_perplexity1 = calculate_fitness([offspring1], solution_df, row_id_column_name)[0]\n    current_perplexity2 = calculate_fitness([offspring2], solution_df, row_id_column_name)[0]\n\n    if not accept_worse_solution(current_perplexity1, best_fitness, temperature):\n        offspring1 = parent1  # Revert if worse solution isn't accepted\n\n    if not accept_worse_solution(current_perplexity2, best_fitness, temperature):\n        offspring2 = parent2  # Revert if worse solution isn't accepted\n\n    return offspring1, offspring2\n\n\n\n\ndef simulated_annealing_schedule(initial_temp, cooling_rate, iteration, max_iterations):\n    \"\"\"Calculate the current temperature and mutation probability based on the annealing schedule.\"\"\"\n    temperature = initial_temp * (cooling_rate ** (iteration / max_iterations))\n    return temperature\n\ndef accept_worse_solution(perplexity, best_perplexity, temperature):\n    \"\"\" Accept a worse solution based on the simulated annealing probability. \"\"\"\n    delta = perplexity - best_perplexity\n    if delta < 0:\n        return True  # Always accept a better solution\n    else:\n        probability = math.exp(-delta / temperature)\n        return random.random() < probability\n\n\ndef mutate(individual, mutation_rate, temperature, best_perplexity, current_perplexity):\n    \"\"\" Apply mutation with simulated annealing acceptance criterion. \"\"\"\n    if random.random() < mutation_rate:\n        # Perform mutation (swap two random elements)\n        i, j = random.sample(range(len(individual)), 2)\n        individual[i], individual[j] = individual[j], individual[i]\n        \n        # Check if we should accept this mutation based on temperature\n        if not accept_worse_solution(current_perplexity, best_perplexity, temperature):\n            # Revert mutation if it's not accepted\n            individual[i], individual[j] = individual[j], individual[i]\n\n    return individual\n\n\n\ndef genetic_algorithm(words, solution_df, row_id_column_name, generations=100, population_size=20, mutation_rate=0.1, num_parents=2, log_filename='generation_log.json', fixed_parents=None, num_elites=3, sa_iterations=1000, initial_temp=1000, cooling_rate=0.99, sa_frequency=5):\n    population = create_population(population_size, words)\n    best_solution = None\n    best_fitness = float('inf')\n    logs = []  # To store logs for each iteration\n    stagnation_count = 0  # Counter to track stagnation\n\n    for generation in range(generations):\n        print(f\"Generation {generation + 1}/{generations}\")\n        \n        # Calculate fitness scores for the current population\n        fitness_scores = calculate_fitness(population, solution_df, row_id_column_name)\n\n        # Find the best solution in the current population\n        best_generation_fitness = min(fitness_scores)\n        best_generation_solution = population[fitness_scores.index(best_generation_fitness)]\n\n        # Update the global best solution if necessary\n        if best_generation_fitness < best_fitness:\n            best_fitness = best_generation_fitness\n            best_solution = best_generation_solution\n\n        # Log the generation data (text and perplexity)\n        for i, individual in enumerate(population):\n            permuted_text = ' '.join(individual)\n            logs.append({\n                'generation': generation + 1,\n                'individual_index': i,\n                'permuted_text': permuted_text,\n                'perplexity': fitness_scores[i]  # Ensure we are using the updated fitness_scores\n            })\n\n        # Select parents\n        parents = []\n        if fixed_parents:\n            # Use the manually set first two parents, convert them to word lists if necessary\n            parent1 = fixed_parents[0].split()\n            parent2 = fixed_parents[1].split()\n            parents.extend([parent1, parent2])\n\n            # Fill the remaining parents using tournament selection\n            while len(parents) < num_parents:\n                selected_parents = roulette_wheel_selection(population, fitness_scores, num_parents=num_parents - len(parents))\n                parents.extend(selected_parents)\n        else:\n            # If no fixed parents are set, use tournament selection for all parents\n            parents = roulette_wheel_selection(population, fitness_scores, num_parents=num_parents - len(parents))\n\n        # Create the next generation using crossover and mutation\n        next_generation = []\n        # New mutation handling:\n        for i in range(0, len(parents), 2):  # Ensure we are pairing parents properly\n            offspring1, offspring2 = pmx_crossover(parents[i], parents[i+1], best_fitness, initial_temp, solution_df, row_id_column_name)  # Pass row_id_column_name here\n        \n            # Set current_perplexity based on best fitness (perplexity)\n            current_perplexity = best_fitness  # This is the best fitness we've found so far\n            \n            # Calculate the temperature using the current generation\n            temperature = simulated_annealing_schedule(initial_temp, cooling_rate, generation, generations)\n            \n            # Apply mutation with additional parameters\n            offspring1 = mutate(offspring1, mutation_rate, temperature, best_fitness, current_perplexity)  # Mutate the offspring\n            offspring2 = mutate(offspring2, mutation_rate, temperature, best_fitness, current_perplexity)  # Mutate the offspring\n        \n            next_generation.append(offspring1)  # Add mutated offspring to the next generation\n            next_generation.append(offspring2)  # Add mutated offspring to the next generation\n\n        # Optionally apply elitism to keep the best individuals\n        elites = elitism(population, fitness_scores, num_elites=num_elites)\n        for i, elite in enumerate(elites):\n            elites[i], _ = simulated_annealing_v4(\n    text=elite,\n    temp_start=6.0,\n    temp_end=1.0,\n    cooling_rate=0.85,  # Adjust as needed\n    n_neighbor=2,\n    steps_per_temp=10,\n    verbose=True,  # Enable verbose logging\n    seq_to_choose=None,  # Use all indices\n    factor_acceptance=1.0\n)\n        next_generation.extend(elites)\n\n        population = next_generation\n\n        # Apply Simulated Annealing every `sa_frequency` generations or if a significant improvement is found\n        if generation % sa_frequency == 0:  # Apply SA every `sa_frequency` generations\n            current_solution = ' '.join(best_solution)\n            current_perplexity = best_fitness\n        if generation % 10 == 0:  # Every 10 generations\n            random_individuals = create_population(int(0.2 * population_size), words)\n            population[-len(random_individuals):] = random_individuals\n        if stagnation_count >= 10:\n            mutation_rate = 0.5  # Temporarily increase mutation rate\n        if stagnation_count >= 10:\n            random_individuals = create_population(int(0.5 * population_size), words)\n            population[-len(random_individuals):] = random_individuals\n        if stagnation_count >= 10:\n            best_solution, best_fitness = simulated_annealing_v4(\n    text=text,\n    temp_start=6.0,\n    temp_end=1.0,\n    cooling_rate=0.85,  # Adjust as needed\n    n_neighbor=2,\n    steps_per_temp=10,\n    verbose=True,  # Enable verbose logging\n    seq_to_choose=None,  # Use all indices\n    factor_acceptance=1.0\n)\n\n        \n            # Optionally, you could check if there's been enough improvement to trigger SA\n            if current_perplexity > best_fitness:\n                best_solution, best_fitness = simulated_annealing_v4(\n    text=text,\n    temp_start=6.0,\n    temp_end=1.0,\n    cooling_rate=0.85,  # Adjust as needed\n    n_neighbor=2,\n    steps_per_temp=10,\n    verbose=True,  # Enable verbose logging\n    seq_to_choose=None,  # Use all indices\n    factor_acceptance=1.0\n)\n    # Save the logs to a JSON file\n        with open(log_filename, 'w') as f:\n            json.dump(logs, f, indent=4)\n\n    # Return the best solution found\n    return ' '.join(best_solution), best_fitness\n\n\n\n# Words list\nwords = words_4  # Assuming 'words_1' is your list of words\n# Create a dummy solution DataFrame (replace with actual solution dataframe)\nsolution_df = pd.DataFrame({\n    'id': [0],\n    'text': \"words\"\n})\n\n# Apply the genetic algorithm, passing the fixed_parents\nbest_solution, best_fitness = genetic_algorithm(\n    words, solution_df, row_id_column_name=\"id\", \n    generations=100, \n    population_size=50, \n    mutation_rate=0.2,  # Higher mutation rate\n    log_filename=\"/kaggle/working/genetic_algorithm_log.json\", \n    fixed_parents=None, \n    num_elites=5,\n    sa_iterations=500,  # More SA iterations\n    initial_temp=500,  # Higher initial temperature\n    cooling_rate=0.98,  # Slower cooling\n    sa_frequency=10  # More frequent SA application\n)\n\n\nprint()\nprint(f\"Best permutation: {best_solution}\")\nprint(f\"Best perplexity: {best_fitness}\")\nprint(f\"Time taken: {time.time() - start_time:.2f} seconds\")\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-01-14T04:37:30.492911Z","iopub.execute_input":"2025-01-14T04:37:30.493256Z","iopub.status.idle":"2025-01-14T04:38:07.941488Z","shell.execute_reply.started":"2025-01-14T04:37:30.493230Z","shell.execute_reply":"2025-01-14T04:38:07.939718Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"#words_1\nfixed_parents = ['reindeer sleep walk the night and drive mistletoe scrooge laugh chimney jump elf bake gingerbread family give advent fireplace ornament', 'ornament mistletoe fireplace chimney and advent elf the family gingerbread reindeer scrooge walk give jump drive bake night sleep laugh']  # Parents are the first two individuals","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-01-12T23:09:46.751874Z","iopub.execute_input":"2025-01-12T23:09:46.752157Z","iopub.status.idle":"2025-01-12T23:09:46.755816Z","shell.execute_reply.started":"2025-01-12T23:09:46.752136Z","shell.execute_reply":"2025-01-12T23:09:46.754946Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"fixed_parents=None","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-01-14T04:31:47.839006Z","iopub.execute_input":"2025-01-14T04:31:47.839370Z","iopub.status.idle":"2025-01-14T04:31:47.843467Z","shell.execute_reply.started":"2025-01-14T04:31:47.839339Z","shell.execute_reply":"2025-01-14T04:31:47.842374Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import pickle\n\nwith open('past.pickle', 'wb') as f:\n    pickle.dump(past, f, protocol=pickle.HIGHEST_PROTOCOL)","metadata":{"trusted":true},"outputs":[],"execution_count":null}]}