CN107678554B - Method and system for layout of mobile phone keyboard - Google Patents

Abstract

The invention discloses a method and a system for mobile phone keyboard layout, which comprises the steps of firstly randomly generating an initial population containing a plurality of individuals, setting iteration times, and obtaining English sentences input by users, wherein the individuals represent the arrangement form of 26 letters on a Sudoku keyboard, and words in the English sentences represent words required by the users and input by habits; counting the occurrence frequency of letters in English sentences at each position in words; then, processing the individuals in the initial population by adopting a non-dominated multi-target algorithm, selecting the first N individuals with high aggregation degree to add into the evolved population, and finishing one-time evolution; judging whether the evolution times are less than the iteration times; if so, processing the individuals in the evolved population by adopting a non-dominated multi-target algorithm; and if not, outputting the individual with the maximum aggregation in the evolved population as the optimal individual. Therefore, the method or the system provided by the invention can rearrange the keyboard pattern of the mobile phone based on the user requirement and the user habit, reduce spelling conflicts and improve the input efficiency.

Description

Method and system for layout of mobile phone keyboard

technical field

The present invention relates to the field of artificial intelligence, in particular to a method and system for a mobile phone keyboard layout based on user requirements.

Background technique

With the development of modern science and technology, mobile phones are widely recognized as the "fifth media" after newspapers, radio, television, and the Internet, and they have a larger and larger user group. With the popularity of smart phones, more and more people use mobile phones as a basic, simple, fast and efficient office tool. On the morning subway, among the crowds waiting to cross the road, and even the students running around the campus, everyone is using their mobile phones to quickly tap the keyboard and do their own work. At this time, the efficiency of mobile phone input is particularly important. According to the survey, the number of people who use the mobile phone Jiugongge input method accounts for about 50% of the total number of mobile phone users.

In the existing mobile phone Jiugongge keyboard sorting, the characters are simply distributed in the order of A-Z. When we want to enter the character "Li", a series of unnecessary invalid characters such as "Ji" will appear, which requires us to spend Timing has long greatly increased the time people spend typing. Therefore, how to improve the efficiency of mobile phone input and reduce typing time is an urgent problem to be solved in the field of artificial intelligence.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a method and system for a mobile phone keyboard layout based on user requirements, which can reduce spelling conflicts, reduce input time, and improve input efficiency.

For achieving the above object, the present invention provides the following scheme:

A method for layout of a mobile phone keyboard, the method comprising:

Randomly generate an initial population containing a plurality of individuals; the individual represents the arrangement of 26 letters on the nine-square keyboard; the arrangement of different individuals is different;

Obtain the English sentence input by the user; the English sentence contains a plurality of words;

Get the frequency of each letter in each position in the word;

Get the number of iterations;

Perform mating, recombination, and mutation processing on the individuals in the initial population to obtain a new individual, and add the new individual to the initial population to obtain a mutant population;

According to the frequency, calculate the first target value and the second target value of each individual in the variant population;

According to the first target value and the second target value of each of the individuals, obtain a first-layer non-dominated individual set;

Judging whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtain a first judgment result;

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, then according to the number of the individuals except the individuals in the first-layer non-dominated individual set a target value and a second target value, obtain the second-layer non-dominated individual set, add the individuals in the second-layer non-dominated individual set to the first-layer non-dominated individual set, and update the first layer After the set of non-dominated individuals, return to the step of judging whether the number of individuals in the set of non-dominated individuals of the first layer is greater than or equal to N, and obtain the first judgment result;

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N, then calculate the aggregation degree of each individual in the first-layer non-dominated individual set, and according to each Arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of the individuals, select the first N individuals from the first-layer non-dominated individual set after the arrangement to join the evolutionary population, and complete an evolution ;

Judging whether the number of evolutions is less than the number of iterations, and obtaining a second judgment result;

If the second judgment result indicates that the number of evolutions is less than the number of iterations, returning to the steps of mating, recombining, and mutating the individuals in the initial population, and replacing the individuals in the initial population with the evolutionary individuals in a population;

If the second judgment result indicates that the number of evolutions is greater than or equal to the number of iterations, the individual with the largest aggregation degree in the evolutionary population is output as the optimal individual.

Optionally, calculating the first target value and the second target value of each individual in the mutant population according to the frequency, specifically includes:

Calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

Calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word.

Optionally, performing mating, recombination, and mutation processing on the individuals in the initial population to obtain new individuals, and adding the new individuals to the initial population to obtain a mutant population, specifically including:

Calculate the first target value and the second target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2);

Selecting two of the individuals from the initial population for multiple times for comparison, and moving the individuals with both the first target value and the second target value smaller to the offspring population, until the number of individuals in the offspring population When the set threshold is reached, the selection is stopped to obtain the progeny population;

Perform discrete recombination and mutation operations on each individual in the progeny population to obtain a processed progeny population;

Individuals in the treated progeny population are added to the initial population to obtain a mutant population.

Optionally, obtaining the first-layer non-dominated individual set according to the first target value and the second target value of each individual, specifically includes:

Judging whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtaining a third judgment result; the non-dominated individuals represent individuals in the mutant population whose first target value and second target value are both minimum values ;

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero, moving the individual to the first-layer non-dominated individual set;

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero, the individual is retained in the mutant population.

Optionally, obtaining the second-layer non-dominated individual set according to the first target value and the second target value of each of the individuals except the individuals in the first-layer non-dominated individual set specifically includes:

Determine whether the number of non-dominated individuals of each individual in the remaining population is zero, and obtain a fourth judgment result; the non-dominated individual indicates that the first target value in the remaining population is less than the first target value of the individual and the second target Individuals whose value is less than the second target value of the individual; the remaining population is a population composed of individuals in the mutant population except for the individuals in the first-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is zero, moving the individual to the second-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is not zero, the individual is retained in the remaining population.

Optionally, the calculating the aggregation degree of each individual in the first-layer non-dominated individual set specifically includes:

The aggregation degree of each individual in the first-layer non-dominated individual set is calculated according to formula (3); the formula (3) is: P(n)=[P(n-1)*q ₁ +P(n +1)*q ₁ ]+[P(n-1)*q ₂ +P(n+1)*q ₂ ](2);

In formula (3), P(n) represents the aggregation degree of the nth individual;

The present invention also provides a system for the layout of a mobile phone keyboard, the system comprising:

The initial population generation module is used to randomly generate an initial population containing a plurality of individuals; the individual represents the arrangement of 26 letters on the nine-square keyboard; the arrangement of different individuals is different;

an English sentence acquisition module, used for acquiring an English sentence input by a user; the English sentence contains a plurality of words;

a frequency acquisition module for acquiring the frequency of each letter appearing in each position in the word;

The number of iterations acquisition module is used to obtain the number of iterations;

A mutant population obtaining module, used for mating, recombining, and mutating individuals in the initial population to obtain a new individual, and adding the new individual to the initial population to obtain a mutant population;

a first target value and a second target value calculation module, configured to calculate the first target value and the second target value of each individual in the variant population according to the frequency;

a first-layer non-dominated individual set acquisition module, configured to acquire a first-layer non-dominated individual set according to the first target value and the second target value of each of the individuals;

The first judgment result obtaining module is used for judging whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtains the first judgment result;

The first-layer non-dominated individual set update module is configured to, when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, according to dividing the first-layer non-dominated individual set the first target value and the second target value of each of the individuals outside the individual in the Layer non-dominated individual sets, after updating the first layer of non-dominated individual sets, return to the step of judging whether the number of individuals in the first layer of non-dominated individual sets is greater than or equal to N, and obtain a first judgment result;

An evolutionary population obtaining module, configured to calculate each individual in the first-layer non-dominated individual set when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N and arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual, and select the first N individuals from the arranged first-layer non-dominated individual set to join To the evolutionary population, complete an evolution;

The second judgment result obtaining module is used to judge whether the number of evolution is less than the number of iterations, and obtain the second judgment result;

The evolutionary population individual processing module is used to return to the steps of mating, recombination, and mutation processing for individuals in the initial population when the second judgment result indicates that the evolution times are less than the iteration times, and the initial individuals in the population are replaced with individuals in the evolutionary population;

The optimal individual output module is configured to output the individual with the largest aggregation degree in the evolutionary population as the optimal individual when the second judgment result indicates that the evolution number is greater than or equal to the iteration number.

Optionally, the first target value and the second target value calculation module specifically includes:

The first target value calculation unit is used to calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

The second target value calculation unit is configured to calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word.

Optionally, the variant population obtains a module, which specifically includes:

The first target value and the second target value calculation unit of each individual in the initial population is used to calculate the first target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2). a target value and a second target value;

The offspring population obtaining unit is used to select two individuals from the initial population for multiple comparisons, and move the individuals whose first target value and the second target value are both smaller to the offspring population, until When the number of individuals of the progeny population reaches the set threshold, the selection is stopped to obtain the progeny population;

After processing, the offspring population obtains a unit, which is used to perform discrete recombination and mutation operations on each individual in the offspring population to obtain the processed offspring population;

The mutant population obtaining unit is used for adding the individuals in the treated progeny population to the initial population to obtain the mutant population.

Optionally, the first-layer non-dominated individual set acquisition module specifically includes:

The third judgment result obtaining unit is used to judge whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtain a third judgment result; the non-dominated individuals represent the first target value and the first target value in the mutant population. Individuals whose two target values are both minimum values;

a moving unit, configured to move the individual to the first-layer non-dominated individual set when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero;

A retention unit, used for retaining the individual in the mutant population when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero.

According to the specific embodiments provided by the present invention, the present invention discloses the following technical effects: the present invention provides a method and system for the layout of a mobile phone keyboard, which re-arranges the mobile phone keyboard layout based on user needs and user habits. Among them, the method first randomly generates an initial population with multiple individuals, sets the number of iterations, and obtains the English sentence input by the user. The individual represents the arrangement form of 26 letters on the Jiugongge keyboard. The arrangement form of different individuals is different. The words in the English sentence Words that represent user needs and habitual input, and count the frequency of each letter in the English sentence appearing at each position in the word; then use the tournament algorithm and the genetic mutation algorithm to mate, recombine, and mutate the individuals in the initial population. , obtain the mutant population, and use the non-dominated target algorithm to obtain the first-level non-dominated individual set with the number of individuals greater than or equal to N according to the frequency counted, and calculate the aggregation degree of each individual in the first-level non-dominated individual set, And according to the descending order of the aggregation degree of each individual, select the first N individuals to join the evolutionary population to complete an evolution; finally judge whether the number of evolution is less than the number of iterations, if so, use the championship algorithm and the genetic mutation algorithm to analyze the evolutionary population. Individuals undergo mating, recombination, and mutation processing; if not, the individual with the largest aggregation degree in the evolutionary population is output as the optimal individual. Therefore, the method or system provided by the present invention can rearrange the mobile phone keyboard layout based on user requirements and user habits, reduce spelling conflicts, reduce input time, and improve input efficiency.

In addition, the present invention adopts the non-dominated multi-objective algorithm to solve the optimal individual, improves the running speed and the convergence of the solution set, avoids finding the optimal explanation and falls into the local optimal solution situation, and reduces the complexity of the non-inferior sorting genetic algorithm.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the accompanying drawings required in the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some of the present invention. In the embodiments, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative labor.

1 is a schematic flowchart of a mobile phone keyboard layout method according to an embodiment of the present invention;

2 is a schematic diagram of the alphabet layout of a mobile phone keyboard according to an embodiment of the present invention;

FIG. 3 is a schematic structural diagram of a mobile phone keyboard layout system according to an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

The purpose of the present invention is to provide a method and system for a mobile phone keyboard layout based on user requirements, which can reduce spelling conflicts, reduce input time, and improve input efficiency.

In order to make the above objects, features and advantages of the present invention more clearly understood, the present invention will be described in further detail below with reference to the accompanying drawings and specific embodiments.

Example 1

FIG. 1 is a schematic flowchart of a mobile phone keyboard layout method according to an embodiment of the present invention. As shown in FIG. 1 , the decryption method provided by the present invention specifically includes the following steps:

Step 101: Randomly generate an initial population containing a plurality of individuals; the individuals represent the arrangement form of 26 letters on the nine-square keyboard; the arrangement forms of different individuals are different.

Step 102: Acquire an English sentence input by the user; the English sentence includes a plurality of words. In this embodiment of the present invention, for the convenience of description, words in English sentences are used to represent words that users are accustomed to input.

Step 103: Obtain the frequency of each letter appearing in each position in the word.

Step 104: Obtain the number of iterations.

Step 105: Perform mating, recombination, and mutation processing on the individuals in the initial population to obtain new individuals, and add the new individuals to the initial population to obtain a mutant population.

Step 106: Calculate the first target value and the second target value of each individual in the mutant population according to the frequency.

Step 107: Obtain a first-layer non-dominated individual set according to the first target value and the second target value of each of the individuals.

Step 108: Determine whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtain a first judgment result.

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, step 109 is executed.

Step 109: According to the first target value and the second target value of each of the individuals except the individuals in the first-layer non-dominated individual set, obtain a second-layer non-dominated individual set, and use the second The individuals in the set of non-dominated individuals of the layer are added to the set of non-dominated individuals of the first layer, and the set of non-dominated individuals of the first layer is updated; after updating the set of non-dominated individuals of the first layer, return to step 108 .

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N, step 110 is executed.

Step 110: Calculate the aggregation degree of each individual in the first-layer non-dominated individual set, and arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual. Select the first N individuals from the first-layer non-dominated individual set to be added to the evolutionary population to complete an evolution. The evolutionary population is composed of the first N individuals in the set of first-level non-dominated individuals after the arrangement.

Step 111: Determine whether the number of evolutions is less than the number of iterations, and obtain a second judgment result.

If the second judgment result indicates that the number of evolutions is less than the number of iterations, step 112 is executed,

Step 112: After replacing the individuals in the initial population with individuals in the evolutionary population, step 105 is performed.

If the second judgment result indicates that the number of evolutions is greater than or equal to the number of iterations, step 113 is executed.

Step 113: Output the individual with the largest aggregation degree in the evolutionary population as the optimal individual.

Wherein, step 106 specifically includes:

Calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

Calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word.

Step 105 specifically includes:

Calculate the first target value and the second target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2);

Selecting two of the individuals from the initial population for multiple times for comparison, and moving the individuals with both the first target value and the second target value smaller to the offspring population, until the number of individuals in the offspring population When the set threshold is reached, the selection is stopped to obtain the progeny population;

Perform discrete recombination and mutation operations on each individual in the progeny population to obtain a processed progeny population;

Individuals in the treated progeny population are added to the initial population to obtain a mutant population.

Step 107 specifically includes:

Judging whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtaining a third judgment result;

The non-dominated individual represents an individual whose first target value and second target value are both minimum values in the mutant population.

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero, moving the individual to the first-layer non-dominated individual set;

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero, the individual is retained in the mutant population.

Step 109 specifically includes:

Determine whether the number of non-dominated individuals of each individual in the remaining population is zero, and obtain a fourth judgment result; the non-dominated individual indicates that the first target value in the remaining population is less than the first target value of the individual and the second target Individuals whose value is less than the second target value of the individual; the remaining population is a population composed of individuals in the mutant population except for the individuals in the first-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is zero, moving the individual to the second-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is not zero, the individual is retained in the remaining population.

According to the above judgment result, the second-layer non-dominated individual set is obtained, the individuals in the second-layer non-dominated individual set are added to the first-layer non-dominated individual set, and the first-layer non-dominated individual set is updated After collection, go back to step 108.

Step 110 specifically includes:

The aggregation degree of each individual in the first-layer non-dominated individual set is calculated according to formula (3); the formula (3) is: P(n)=[P(n-1)*q ₁ +P(n +1)*q ₁ ]+[P(n-1)*q ₂ +P(n+1)*q ₂ ](3);

In formula (3), P(n) represents the aggregation degree of the nth individual;

Arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual, select the first N individuals from the first-layer non-dominated individual set after the arrangement to join the evolutionary population, and complete an evolution.

Embodiment 2

In order to verify a method for a mobile phone keyboard layout based on user requirements provided by the present invention, which can reduce spelling conflicts, reduce input time, and improve input efficiency, the following specific embodiments are described.

The embodiment of the present invention also adopts the method provided by the first embodiment, and the specific content is as follows:

Step 1: Get an English sentence, the English sentence is "I'm happy to meet you, will you take a seat at the head of table? It's an informal dinner, please don't standon ceremony, would you like to have some chicken?". In this embodiment of the present invention, for the convenience of description, words in English sentences are used to represent words that users are accustomed to input.

Step 2: Count the frequency of each letter in the English sentence appearing in each position in the word, and assign a decreasing proportion to each position. The frequency of the statistics is shown in Table 1.

Table 1 Frequency table of each letter in each position in the word

The third step: randomly generate an initial population containing a plurality of individuals; the individual represents the arrangement of 26 letters on the nine-square keyboard; the arrangement of different individuals is different; in the embodiment of the present invention, the number of evolutions is 300, and the initial The number of individuals in the population is 100.

Step 4: Process the individuals in the initial population to obtain new individuals, and combine the new individuals with the initial population to obtain a variant population, which includes:

Firstly, individual selection is carried out by using the tournament selection method, secondly, discrete recombination is performed on the selected individuals, and finally chromosome mutation is performed on the discretely recombined individuals to obtain a new individual after the mutation, and the new individual is merged with the initial population to obtain a mutant population.

Among them, the basic steps of the tournament selection method are:

(1) randomly select n individuals from the initial population (n is 50 in this embodiment).

(2) Calculate the fitness value of each individual, and select the individual with the highest fitness to enter the offspring population. The first target value and the second target value of each individual are calculated according to formula (1) and formula (2), and the individual with high fitness indicates that the first target value is smaller than the first target value and the second target value of the individual Individuals that are less than the individual's second target value.

(3) Repeat step (2) until the size of the offspring population reaches the set value of 25.

Discrete Recombination:

Swap the value of a variable between individuals in the offspring population, for example:

Parent 1: 12 25 5

Parent entity 2:123 4 34

Each variable of the sub-individual can randomly select the parent individual according to the same general theory, for example, a sub-individual after discrete recombination is:

Child 1:123 4 5

Child 2:12 4 5

Chromosomal mutation: mutate a certain bit of the individual after discrete recombination with a probability of 0.1-0.0001, and the mutation value is each number of 1-9.

In summary, after tournament selection, discrete recombination and chromosome mutation operations, the number of individuals in the mutant population is 125.

Step 5: Calculate the first target value and the second target value of each individual in the variant population according to the frequency counted in Table 1, specifically:

Calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

Calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word.

Step 6: According to the first target value and the second target value of each of the individuals, obtain a set of non-dominated individuals of the first layer. The sixth step specifically includes: judging whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtaining a third judgment result; the non-dominated individuals indicate that the first target value in the mutant population is smaller than the an individual whose first target value for an individual and whose second target value is less than the second target value for said individual;

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero, moving the individual to the first-layer non-dominated individual set;

If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero, the individual is retained in the mutant population.

Step 7: Determine whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtain a first judgment result. In this embodiment, N is 50;

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, step 8 is performed.

Step 8: According to the first target value and the second target value of each of the individuals except the individuals in the first-layer non-dominated individual set, obtain the second-layer non-dominated individual set, and use the The individuals in the second-layer non-dominated individual set are added to the first-layer non-dominated individual set, and the first-layer non-dominated individual set is updated; after updating the first-layer non-dominated individual set, return to step 7 to continue judging .

The eighth step specifically includes judging whether the number of non-dominated individuals in each individual in the remaining population is zero, and obtaining a fourth judgment result; the non-dominated individual indicates that the first target value and the second target value in the mutant population are both equal. is the individual with the minimum value; the remaining population is a population composed of individuals in the mutant population except for the individuals in the first-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is zero, moving the individual to the second-layer non-dominated individual set;

If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is not zero, the individual is retained in the remaining population.

According to the above judgment result, the second-layer non-dominated individual set is obtained, the individuals in the second-layer non-dominated individual set are added to the first-layer non-dominated individual set, and the first-layer non-dominated individual set is updated After collection, go back to step 7 to continue judging.

If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N, step 9 is performed.

Step 9: Calculate the aggregation degree of each individual in the first-layer non-dominated individual set according to formula (3), and arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual. individuals, and select the first N individuals from the set of non-dominated individuals of the first layer after the arrangement to be added to the evolutionary population to complete an evolution. The evolutionary population is composed of the first N individuals in the set of first-level non-dominated individuals after the arrangement.

The formula (3) is: P(n)=[P(n-1)*q ₁ +P(n+1)*q ₁ ]+[P(n-1)*q ₂ +P(n+ 1)*q ₂ ](3);

In formula (3), P(n) represents the aggregation degree of the nth individual;

Step 10: Judging whether the number of evolutions is less than the number of iterations 300, and obtaining a second judgment result.

If the second judgment result indicates that the number of evolutions is less than the number of iterations 300, step 11 is performed,

Step 11: After replacing the individuals in the initial population with individuals in the evolutionary population, perform the fourth step.

If the second judgment result indicates that the number of evolutions is greater than or equal to the number of iterations, the twelfth step is performed.

The twelfth step: output the individual with the largest aggregation degree in the evolutionary population as the optimal individual. The form of the optimal individual is shown in Figure 2, that is, the output individual code is 2 1 3 4 3 4 2 5 6 5 1 7 8 8 9 8 8 9 1 7 96 2 3 7 6 9.

The nine-square-grid keyboard obtained by the embodiment of the present invention reduces the conflict during input. For example, when inputting the word "meet", just press "83" to see on the screen that there is only the word "meet" we need in the options. There will be conflicts with other words.

In addition, by observing people's input habits and adding complete keyboard keys, the design is shown in Figure 2. Among them, the send key is located in the lower right corner of the keyboard arrangement, and the set key size is large enough to reduce the probability of people's wrong press; and according to statistical surveys, the usage rate of the space bar in people's spelling is as high as 25%, so put the space bar Arranged at the bottom of the keyboard, and the size is large enough, it can make people's input more convenient and effective.

Embodiment 3

In order to achieve the above object, the present invention also provides a system for the layout of a mobile phone keyboard. FIG. 3 is a schematic structural diagram of a mobile phone keyboard layout system according to an embodiment of the present invention. As shown in FIG. 3 , the system includes:

The initial population generation module 301 is used to randomly generate an initial population containing a plurality of individuals; the individuals represent the arrangement form of 26 letters on the nine-square keyboard; the arrangement forms of different individuals are different.

The English sentence obtaining module 302 is configured to obtain the English sentence input by the user; the English sentence includes a plurality of words.

The frequency acquisition module 303 is configured to acquire the frequency of each letter appearing in each position in the word. In this embodiment of the present invention, for the convenience of description, words in English sentences are used to represent words that users are accustomed to input.

The iteration number acquiring module 304 is used to acquire the iteration number.

The mutant population obtaining module 305 is used for mating, recombining, and mutating individuals in the initial population to obtain new individuals, and adding the new individuals to the initial population to obtain a mutant population.

The first target value and the second target value calculation module 306 is configured to calculate the first target value and the second target value of each individual in the variant population according to the frequency.

The first-layer non-dominated individual set obtaining module 307 is configured to obtain the first-layer non-dominated individual set according to the first target value and the second target value of each of the individuals.

The first judgment result obtaining module 308 is configured to judge whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtain a first judgment result.

The first-layer non-dominated individual set updating module 309 is configured to, when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, according to dividing the first-layer non-dominated individual The first target value and the second target value of each individual outside the individual in the set, obtain the second-level non-dominated individual set, and add the individuals in the second-level non-dominated individual set to the first One layer of non-dominated individual sets, after updating the first layer of non-dominated individual sets, return to the step of judging whether the number of individuals in the first layer of non-dominated individual sets is greater than or equal to N, and obtain a first judgment result.

The evolutionary population obtaining module 310 is configured to calculate each non-dominated individual set in the first layer when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N the aggregation degree of individuals, and arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual, and select the first N individuals from the arranged first-layer non-dominated individual set Join the evolutionary population and complete an evolution. The evolutionary population is composed of the first N individuals in the set of first-level non-dominated individuals after the arrangement.

The second judgment result obtaining module 311 is used for judging whether the number of evolutions is less than the number of iterations to obtain a second judgment result.

The evolutionary population individual processing module 312 is configured to return to the steps of mating, recombination, and mutation processing for individuals in the initial population when the second judgment result indicates that the number of evolutions is less than the number of iterations, and the Individuals in the initial population are replaced with individuals in the evolved population.

The optimal individual output module 313 is configured to output the individual with the largest aggregation degree in the evolutionary population as the optimal individual when the second judgment result indicates that the evolution number is greater than or equal to the iteration number.

Wherein, the first target value and the second target value calculation module 306 specifically includes:

The first target value calculation unit is used to calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

The second target value calculation unit is configured to calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word.

The variant population obtaining module 305 specifically includes:

The first target value and the second target value calculation unit of each individual in the initial population is used to calculate the first target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2). a target value and a second target value.

The offspring population obtaining unit is used to select two individuals from the initial population for multiple comparisons, and move the individuals whose first target value and the second target value are both smaller to the offspring population, until When the number of individuals of the progeny population reaches the set threshold, the selection is stopped, and the progeny population is obtained.

After processing, the offspring population obtains a unit, which is used to perform discrete recombination and mutation operations on each individual in the offspring population to obtain the processed offspring population.

The mutant population obtaining unit is used for adding the individuals in the treated progeny population to the initial population to obtain the mutant population.

The first-layer non-dominated individual set acquisition module 307 specifically includes:

The third judgment result obtaining unit is used to judge whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtain a third judgment result; the non-dominated individual indicates that the first target value in the mutant population is less than the An individual whose first target value for the individual and whose second target value is less than the individual's second target value.

A moving unit, configured to move the individual to the first-level non-dominated individual set when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero.

A retention unit, used for retaining the individual in the mutant population when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero.

The first-layer non-dominated individual set update module 309 specifically includes:

The fourth judgment result obtaining unit is used to judge whether the number of non-dominated individuals of each individual in the remaining population is zero, and obtain a fourth judgment result; the non-dominated individuals represent the first target value and the second target in the mutant population The values are all individuals with the minimum value; the remaining population is a population composed of individuals in the mutant population except the individuals in the first-level non-dominated individual set.

A unit for obtaining a set of non-dominated individuals in the second layer is used to move the individual to the second layer when the fourth judgment result indicates that the number of non-dominated individuals in each individual in the remaining population is zero. The set of non-dominated individuals is obtained, and the second-level set of non-dominated individuals is obtained.

A remaining population retention unit, configured to retain the individual in the remaining population when the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is not zero.

The first-layer non-dominated individual set updating unit is used to add the individuals in the second-layer non-dominated individual set to the first-layer non-dominated individual set, and after updating the first-layer non-dominated individual set, return To the step of judging whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, obtaining a first judgment result.

The evolutionary population obtains module 310, which specifically includes:

an individual aggregation degree calculation unit, configured to calculate the aggregation degree of each individual in the first-layer non-dominated individual set according to formula (3); the formula (3) is: P(n)=[P(n-1 )*q ₁ +P(n+1)*q ₁ ]+[P(n-1)*q ₂ +P(n+1)*q ₂ ](3);

In formula (3), P(n) represents the aggregation degree of the nth individual;

An evolutionary population obtaining unit, used for arranging each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual, and selecting the first N from the first-layer non-dominated individual set after the arrangement An individual joins the evolutionary population and completes an evolution.

Through the description of the above embodiments, the method or system provided by the present invention can rearrange the mobile phone keyboard layout based on user requirements and user habits, reduce spelling conflicts, reduce input time, and improve input efficiency.

In addition, the present invention adopts the non-dominated multi-objective algorithm to solve the optimal individual, improves the running speed and the convergence of the solution set, avoids finding the optimal explanation and falls into the local optimal solution situation, and reduces the complexity of the non-inferior sorting genetic algorithm

The various embodiments in this specification are described in a progressive manner, and each embodiment focuses on the differences from other embodiments, and the same and similar parts between the various embodiments can be referred to each other. For the system disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and the relevant part can be referred to the description of the method.

In this paper, specific examples are used to illustrate the principles and implementations of the present invention. The descriptions of the above embodiments are only used to help understand the methods and core ideas of the present invention; meanwhile, for those skilled in the art, according to the present invention There will be changes in the specific implementation and application scope. In conclusion, the contents of this specification should not be construed as limiting the present invention.

Claims (7)

1. a method of mobile phone keyboard layout, is characterized in that, described method comprises: Randomly generate an initial population containing a plurality of individuals; the individual represents the arrangement of 26 letters on the nine-square keyboard; the arrangement of different individuals is different; Obtain the English sentence input by the user; the English sentence contains a plurality of words; Get the frequency of each letter in each position in the word; Get the number of iterations; Perform mating, recombination, and mutation processing on the individuals in the initial population to obtain a new individual, and add the new individual to the initial population to obtain a mutant population; Calculate the first target value and the second target value of each individual in the variant population according to the frequency; calculate the first target value of each individual in the variant population according to formula (1); the formula (1) )for:

Calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word; According to the first target value and the second target value of each of the individuals, obtain a first-layer non-dominated individual set; Judging whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtain a first judgment result; If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, then according to the number of the individuals except the individuals in the first-layer non-dominated individual set a target value and a second target value, obtain the second-layer non-dominated individual set, add the individuals in the second-layer non-dominated individual set to the first-layer non-dominated individual set, and update the first layer After the set of non-dominated individuals, return to the step of judging whether the number of individuals in the set of non-dominated individuals of the first layer is greater than or equal to N, and obtain the first judgment result; If the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N, then calculate the aggregation degree of each individual in the first-layer non-dominated individual set, and according to each Arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of the individuals, select the first N individuals from the first-layer non-dominated individual set after the arrangement to join the evolutionary population, and complete an evolution ; Calculate the aggregation degree of each individual in the first-layer non-dominated individual set according to formula (3); the formula (3) is: P(n)=[P(n-1)*q ₁ +P( n+1)*q ₁ ]+[P(n-1)*q ₂ +P(n+1)*q ₂ ](3); in formula (3), P(n) represents the nth individual’s agglomeration;

Judging whether the number of evolutions is less than the number of iterations, and obtaining a second judgment result; If the second judgment result indicates that the number of evolutions is less than the number of iterations, returning to the steps of mating, recombining, and mutating the individuals in the initial population, and replacing the individuals in the initial population with the evolutionary individuals in a population; If the second judgment result indicates that the number of evolutions is greater than or equal to the number of iterations, the individual with the largest aggregation degree in the evolutionary population is output as the optimal individual. 2. The method according to claim 1, characterized in that, the individuals in the initial population are subjected to mating, recombination, and mutation processing to obtain new individuals, and the new individuals are added to the initial population , the mutant population is obtained, including: Calculate the first target value and the second target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2); Selecting two of the individuals from the initial population for multiple times for comparison, and moving the individuals with both the first target value and the second target value smaller to the offspring population, until the number of individuals in the offspring population When the set threshold is reached, the selection is stopped to obtain the progeny population; Perform discrete recombination and mutation operations on each individual in the progeny population to obtain a processed progeny population; Individuals in the treated progeny population are added to the initial population to obtain a mutant population. 3. The method according to claim 1, characterized in that, acquiring the first-layer non-dominated individual set according to the first target value and the second target value of each individual, specifically comprising: Judging whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtaining a third judgment result; the non-dominated individuals represent individuals in the mutant population whose first target value and second target value are both minimum values ; If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero, moving the individual to the first-layer non-dominated individual set; If the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero, the individual is retained in the mutant population. 4 . The method according to claim 3 , wherein, according to the first target value and the second target value of each of the individuals except the individuals in the first-layer non-dominated individual set, the first target value is obtained. 5 . The second-level set of non-dominated individuals, including: Determine whether the number of non-dominated individuals of each individual in the remaining population is zero, and obtain a fourth judgment result; the non-dominated individual indicates that the first target value in the remaining population is less than the first target value of the individual and the second target Individuals whose value is less than the second target value of the individual; the remaining population is a population composed of individuals in the mutant population except for the individuals in the first-layer non-dominated individual set; If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is zero, moving the individual to the second-layer non-dominated individual set; If the fourth judgment result indicates that the number of non-dominated individuals of each individual in the remaining population is not zero, the individual is retained in the remaining population. 5. A system for mobile phone keyboard layout, wherein the system comprises: The initial population generation module is used to randomly generate an initial population containing a plurality of individuals; the individual represents the arrangement of 26 letters on the nine-square keyboard; the arrangement of different individuals is different; an English sentence acquisition module for acquiring an English sentence input by a user; the English sentence contains multiple words; a frequency acquisition module for acquiring the frequency of each letter appearing in each position in the word; The number of iterations acquisition module is used to obtain the number of iterations; A mutant population obtaining module, used for mating, recombining, and mutating individuals in the initial population to obtain a new individual, and adding the new individual to the initial population to obtain a mutant population; The first target value and the second target value calculation module is used to calculate the first target value and the second target value of each individual in the mutant population according to the frequency; specifically, it includes: a first target value calculation unit, which uses to calculate the first target value of each individual in the variant population according to formula (1); the formula (1) is:

The second target value calculation unit is configured to calculate the second target value of each individual in the variant population according to formula (2); the formula (2) is:

In formula (1), (2), n represents the nth individual; m represents the mth key on the nine-square keyboard, and the nine-square keyboard is provided with nine keys, and each key is provided with three or four letters; p _ij represents the probability that the j-th letter in each key appears in the i-th position in the word; λ _i represents the proportion of the i-th position in the word; g(m) represents the minimum k of all letters in the m-th key value, g(m)=mink; k represents the maximum value of the position of the letter in the word; a first-layer non-dominated individual set acquisition module, configured to acquire a first-layer non-dominated individual set according to the first target value and the second target value of each of the individuals; The first judgment result obtaining module is used for judging whether the number of individuals in the first-layer non-dominated individual set is greater than or equal to N, and obtains the first judgment result; The first-layer non-dominated individual set update module is configured to, when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is less than the N, according to dividing the first-layer non-dominated individual set the first target value and the second target value of each of the individuals outside the individual in the Layer non-dominated individual sets, after updating the first layer of non-dominated individual sets, return to the step of judging whether the number of individuals in the first layer of non-dominated individual sets is greater than or equal to N, and obtain a first judgment result; An evolutionary population obtaining module, configured to calculate each individual in the first-layer non-dominated individual set when the first judgment result indicates that the number of individuals in the first-layer non-dominated individual set is greater than or equal to the N and arrange each individual in the first-layer non-dominated individual set in descending order according to the aggregation degree of each individual, and select the first N individuals from the arranged first-layer non-dominated individual set to join To the evolutionary population, complete an evolution; The second judgment result obtaining module is used to judge whether the number of evolution is less than the number of iterations, and obtain the second judgment result; The evolutionary population individual processing module is used to return to the steps of mating, recombination, and mutation processing for individuals in the initial population when the second judgment result indicates that the evolution times are less than the iteration times, and the initial individuals in the population are replaced with individuals in the evolutionary population; The optimal individual output module is configured to output the individual with the largest aggregation degree in the evolutionary population as the optimal individual when the second judgment result indicates that the evolution number is greater than or equal to the iteration number. 6. The system according to claim 5, wherein the variant population obtaining module specifically comprises: The first target value and the second target value calculation unit of each individual in the initial population is used to calculate the first target value of each individual in the initial population according to the frequency, the formula (1) and the formula (2). a target value and a second target value; The offspring population obtaining unit is used to select two individuals from the initial population for multiple comparisons, and move the individuals whose first target value and the second target value are both smaller to the offspring population, until When the number of individuals of the progeny population reaches the set threshold, the selection is stopped to obtain the progeny population; After processing, the offspring population obtains a unit, which is used to perform discrete recombination and mutation operations on each individual in the offspring population to obtain the processed offspring population; The mutant population obtaining unit is used for adding the individuals in the treated progeny population to the initial population to obtain the mutant population. 7. The system according to claim 5, wherein the first-layer non-dominated individual set acquisition module specifically comprises: The third judgment result obtaining unit is used to judge whether the number of non-dominated individuals of each individual in the mutant population is zero, and obtain a third judgment result; the non-dominated individuals represent the first target value and the first target value in the mutant population. Individuals whose two target values are both minimum values; a moving unit, configured to move the individual to the first-layer non-dominated individual set when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is zero; A retention unit, used for retaining the individual in the mutant population when the third judgment result indicates that the number of non-dominated individuals of each individual in the mutant population is not zero.

Images